POJ - 2236 Wireless Network （并查集）

本文主要是介绍POJ - 2236 Wireless Network （并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：http://poj.org/problem?id=2236

题意：n台损坏的计算机分布在二维平面的一些点上，给出n台计算机的位置，给出两种操作，一是修复某台计算机，二是 查询两台计算机之间是否能联络。

分析：好久没做并查集了，一开始想着用深搜，尴尬，后来分析搜索明显超时，明显一道裸的并查集。两台计算机能联络必须满足两个条件，一是距离d’<=d，二是两台计算机完好。（用个标记）并查集的本质是一些有联系的点合并为一个集合，这个集合有唯一的公共祖先。（debug了几天，看来对并查集的本质理解不深刻）

代码：

 

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 1e3+10;
struct node{int x,y,flag;
}node[maxn];
int pre[maxn],n,d,s,e;void init(){for(int i=1;i<=n;pre[i]=i,i++);
}int Find(int x){while(x!=pre[x])x=pre[x];return x;
}int main(){cin>>n>>d;for(int i=1;i<=n;i++){cin>>node[i].x>>node[i].y;node[i].flag=0;}char c;init();while(cin>>c){if(c=='O'){cin>>s;node[s].flag=1;for(int i=1;i<=n;i++){if(i==s) continue;if(Find(i)!=Find(s)&&node[i].flag&&d*d>=((node[i].x-node[s].x)*(node[i].x-node[s].x)+(node[i].y-node[s].y)*(node[i].y-node[s].y)))pre[Find(i)]=Find(s);}}else if(c=='S'){cin>>s>>e;if(Find(s)!=Find(e)) cout<<"FAIL"<<endl;else cout<<"SUCCESS"<<endl;}}
}

 

 

 

 

 

这篇关于POJ - 2236 Wireless Network （并查集）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---