欧美综合国产精品久久丁香,欧美视频在线播放,欧美日韩成人综合

蝸牛の狂奔筆記

對于蝸牛來說，狂奔雖不代表極速，但展現的卻是一種拼盡全力的姿態........

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 閱讀(1000) 評論(2) 編輯收藏引用

@cppexplore
謝謝你的提醒,這些都是北大ACM在線OJ上的題目，呵呵，我們做ACM的習慣把自己過了的題目的代碼記錄下來,供大家學習交流,一般遇到不會的題目,不會的算法,我們也會baidu,google一下,通過看別人的代碼來尋找思路,因為ACM本身是沒有官方標準答案公布的,呵呵,計算機的學習本身就是一個不斷相互學習和交流,共同進步的過程不是嗎,我也看到首頁里面也有很多記錄ACM的文章哈,相信大家都是同我一樣的回復更多評論