pku 2236

2009年7月13日 星期一

题目链接：PKU 2236 Wireless Network

分类：并查集的应用

Code：

 1#include<stdio.h>
 2#include<string.h>
 3#include<math.h>
 4#define max 1005
 5int i,j,parent[max],t,n,d,a,b,f[max];
 6char s[5];
 7double dis[max][max];
 8struct zuobiao
 9{
10    double x,y;
11}pos[max];
12void init(int n)
13{
14    for(j=1;j<=n;j++)parent[j]=-1;
15}
16int find(int x)
17{
18    if(parent[x]<0)return x;
19    else return parent[x]=find(parent[x]);
20}
21void Union(char k)
22{
23    if(k=='O')
24    {
25        f[a]=1;
26        for(j=1;j<=n;j++)
27        {
28            if(a!=j&&f[j]&&dis[a][j]<=d)
29            {
30                int r1=find(a),r2=find(j);
31                if(r1!=r2)     //以root2为根
32                {
33                    parent[r2]+=parent[r1];
34                    parent[r1]=r2;
35                }
36            }
37        }
38    }
39    else
40    {
41        int r1=find(a),r2=find(b);
42        if(r1==r2)printf("SUCCESS\n");
43        else printf("FAIL\n");
44    }
45}
46int main()
47{
48    scanf("%d%d",&n,&d);
49    init(n);
50    memset(f,0,sizeof(f));
51    memset(dis,0,sizeof(dis));
52    for(i=1;i<=n;i++)scanf("%lf%lf",&pos[i].x,&pos[i].y);
53    for(i=1;i<n;i++)
54        for(j=i+1;j<=n;j++)
55        {
56            dis[i][j]=sqrt((pos[i].x-pos[j].x)*(pos[i].x-pos[j].x)+(pos[i].y-pos[j].y)*(pos[i].y-pos[j].y));
57            dis[j][i]=dis[i][j];
58        }
59    while(scanf("%s",s)!=EOF)
60    {
61        if(strcmp(s,"S")==0)scanf("%d%d",&a,&b);
62        else scanf("%d",&a);
63        Union(s[0]);
64    }    
65    return 0;
66}
67

posted on 2009-07-13 23:22 蜗牛也Coding 阅读(959) 评论(2)  编辑 收藏 引用

评论

# re: pku 2236 2009-07-14 11:09 cppexplore

博主，这种整篇都是代码的文章 就不要再往首页上发了。全是代码，很少会有人看的，很多人订阅了首页，尽量不要浪费大家的时间。  回复  更多评论   

# re: pku 2236 2009-07-14 14:19 蜗牛也Coding

@cppexplore
谢谢你的提醒,这些都是北大ACM在线OJ上的题目，呵呵，我们做ACM的习惯把自己过了的题目的代码记录下来,供大家学习交流,一般遇到不会的题目,不会的算法,我们也会baidu,google一下,通过看别人的代码来寻找思路,因为ACM本身是没有官方标准答案公布的,呵呵,计算机的学习本身就是一个不断相互学习和交流,共同进步的过程不是吗,我也看到首页里面也有很多记录ACM的文章哈,相信大家都是同我一样的  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年10月>
日一二三四五六
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜