国产在线高清精品,欧美激情视频网站,亚洲尤物视频网

pku 2236

2009年7月13日星期一

題目鏈接：PKU 2236 Wireless Network

分類：并查集的應(yīng)用

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

評(píng)論

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

博主，這種整篇都是代碼的文章就不要再往首頁(yè)上發(fā)了。全是代碼，很少會(huì)有人看的，很多人訂閱了首頁(yè)，盡量不要浪費(fèi)大家的時(shí)間。回復(fù) 更多評(píng)論

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

@cppexplore
謝謝你的提醒,這些都是北大ACM在線OJ上的題目，呵呵，我們做ACM的習(xí)慣把自己過了的題目的代碼記錄下來(lái),供大家學(xué)習(xí)交流,一般遇到不會(huì)的題目,不會(huì)的算法,我們也會(huì)baidu,google一下,通過看別人的代碼來(lái)尋找思路,因?yàn)锳CM本身是沒有官方標(biāo)準(zhǔn)答案公布的,呵呵,計(jì)算機(jī)的學(xué)習(xí)本身就是一個(gè)不斷相互學(xué)習(xí)和交流,共同進(jìn)步的過程不是嗎,我也看到首頁(yè)里面也有很多記錄ACM的文章哈,相信大家都是同我一樣的回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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

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

pku 2236

評(píng)論

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜