問題：

地震發(fā)生在東南亞。 ACM（亞洲合作醫(yī)療團(tuán)隊(duì)）已經(jīng)與膝上電腦建立了無線網(wǎng)絡(luò)，但是一次意外的余震襲擊，網(wǎng)絡(luò)中的所有計(jì)算機(jī)都被打破了。計(jì)算機(jī)一個(gè)接一個(gè)地修復(fù)，網(wǎng)絡(luò)逐漸開始工作。由于硬件限制，每臺(tái)計(jì)算機(jī)只能直接與距離它不遠(yuǎn)的計(jì)算機(jī)進(jìn)行通信。但是，每臺(tái)計(jì)算機(jī)都可以被視為兩臺(tái)計(jì)算機(jī)之間通信的中介，也就是說，如果計(jì)算機(jī)A和計(jì)算機(jī)B可以直接通信，或者計(jì)算機(jī)C可以與A和b進(jìn)行通信，則計(jì)算機(jī)A和計(jì)算機(jī)B可以進(jìn)行通信。

在修復(fù)網(wǎng)絡(luò)的過程中，工作人員可以隨時(shí)進(jìn)行兩種操作，修復(fù)計(jì)算機(jī)或測試兩臺(tái)計(jì)算機(jī)是否可以通信。你的工作是回答所有的測試操作。
輸入
第一行包含兩個(gè)整數(shù)N和d（1 <= N <= 1001,0 <= d <= 20000）。這里N是計(jì)算機(jī)的數(shù)量，編號(hào)從1到N，D是兩臺(tái)計(jì)算機(jī)可以直接通信的最大距離。在接下來的N行中，每行包含兩個(gè)整數(shù)xi，yi（0 <= xi，yi <= 10000），這是N臺(tái)計(jì)算機(jī)的坐標(biāo)。從第（N + 1）行到輸入結(jié)束，有一些操作，這些操作是一個(gè)接一個(gè)地執(zhí)行的。每行包含以下兩種格式之一的操作：
1.“O p”（1 <= p <= N），表示修復(fù)計(jì)算機(jī)p。
2.“S p q”（1 <= p，q <= N），這意味著測試計(jì)算機(jī)p和q是否可以通信。

輸入不會(huì)超過300000行。
產(chǎn)量
對(duì)于每個(gè)測試操作，如果兩臺(tái)計(jì)算機(jī)可以通信則打印“SUCCESS”，否則打印“FAIL”。
Sample Input
（注意0和o啊。。）

4 1 0 1 0 2 0 3 0 4 O 1 O 2 O 4 S 1 4 O 3 S 1 4

Sample Output
FAIL
SUCCESS

分析與解答：

我一開始沒讀懂提，1和2和4修好了，那2可以與3連，4可以與3連為啥1和四不能連？后來我明白了，修好的電腦能連與他距離小于等于d的修好的電腦。而不是說小于d的電腦都能與之連。就是說，可以通信的計(jì)算機(jī)一定都是已經(jīng)修好的計(jì)算機(jī)，而且兩臺(tái)修好的計(jì)算機(jī)的距離還必須小于等于給定的那個(gè)距離。

編號(hào)從1-n，只不過這里的電腦多了個(gè)坐標(biāo)，多了個(gè)距離的判斷。
并查集里放的是相連的電腦編號(hào)，最后找也是找電腦編號(hào)的根

代碼參考：https://blog.csdn.net/superxtong/article/details/51875835

#include<cstdio> #include<cstring> int pre[10100 ]; int find(int x) //查找根節(jié)點(diǎn) { int r=x;while ( pre[r] != r ) //返回根節(jié)點(diǎn) rr=pre[r];int i=x , j ;while( i != r ) //路徑壓縮{j = pre[ i ]; //j是i的原來的父結(jié)點(diǎn) pre[ i ]= r ; //現(xiàn)在把i的父結(jié)點(diǎn)改成根節(jié)點(diǎn) i=j; //再把j的父節(jié)點(diǎn)改成根節(jié)點(diǎn) }return r ; } void join(int x,int y) //判斷x y是否連通，//如果已經(jīng)連通，就不用管了 如果不連通，就把它們所在的連通分支合并起, {int fx=find(x),fy=find(y);if(fx!=fy)pre[fx ]=fy; } struct xyz{int x;int y; }; xyz a[10086]; int flag[10086]; int main(){memset(flag,0,sizeof(flag));int n,d;scanf("%d%d",&n,&d);for(int i=1;i<=n;++i){pre[i]=i;scanf("%d%d",&a[i].x,&a[i].y);}char ch;while(scanf(" %c",&ch)!=EOF){if(ch=='O'){int k;scanf("%d",&k);flag[k]=1;for(int i=1;i<=n;i++){if(flag[i]&&i!=k){if((a[i].x-a[k].x)*(a[i].x-a[k].x)+(a[i].y-a[k].y)*(a[i].y-a[k].y)<=d*d)join(i,k);}}}if(ch=='S'){int x1,y1;scanf("%d%d",&x1,&y1);if(find(x1)==find(y1))printf("SUCCESS\n");elseprintf("FAIL\n");}} }

總結(jié)

以上是生活随笔為你收集整理的（并查集）Wireless Network的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。