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
5

int i,j,parent[max],t,n,d,a,b,f[max];
6

char s[5];
7

double dis[max][max];
8

struct zuobiao
9

{
10

double x,y;
11

}pos[max];
12

void init(int n)
13

{
14

for(j=1;j<=n;j++)parent[j]=-1;
15

}
16

int find(int x)
17

{
18

if(parent[x]<0)return x;
19

else return parent[x]=find(parent[x]);
20

}
21

void 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

}
46

int 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 阅读(925) 评论(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 知识库博问管理

2009年7月

日

一

二

三

四

五

六

统计

随笔 - 78
文章 - 0
评论 - 96
引用 - 0

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

积分 - 90579
排名 - 259