Wireless Network
题目链接：Click Here~
题目分析：
一道简单的并查集，但是在考虑如何加点的时候被卡了半天。kao！！！后来想用floyd处理连通的，一算O（10^14）啊！！！！！最后，才明白在加点的时候是把当前点（A）的与其他点（B）的距离dist(AB)<=d的加入，而且前提是B点必须是可行的！！就是这里卡了半天。后来发现题目是有提醒的，有一次被英语给坑了(- -;)。there is a computer C that can communicate with both A and B. 意思是通过可行的C连通A,B。开始给理解错了。别的就是基础了，细节看代码。
#include#include #include #include #include using namespace std; const int maxn = 1005; struct Point{ double x,y; }p[maxn]; vector G[maxn]; int n,f[maxn],cnnect[maxn]; void Init() { for(int i = 0;i < maxn;++i) G[i].clear(),f[i] = i,cnnect[i] = 0; } double Distance(Point a,Point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int Find(int x) { if(x==f[x]) return f[x]; return f[x] = Find(f[x]); } void Union(int u,int v) { int a = Find(u),b = Find(v); if(a != b) f[a] = b; } int main() { double d; while(~scanf("%d%lf",&n,&d)) { Init(); for(int i = 1;i <= n;++i) scanf("%lf%lf",&p[i].x,&p[i].y); for(int i = 1;i <= n;++i) for(int j = 1;j <= n;++j){ double dist = Distance(p[i],p[j]); if(dist <= d) G[i].push_back(j); } char str[5]; int x,y; while(~scanf("%s",str)){ if(str[0]=='O'){ scanf("%d",&x); cnnect[x] = 1; for(int i = 0;i < (int)G[x].size();++i){ y = G[x][i]; if(cnnect[y]) //kao !!!!!!!!!!! Union(x,y); } } else{ scanf("%d%d",&x,&y); int a = Find(x),b = Find(y); if(a == b) puts("SUCCESS"); else puts("FAIL"); } } } return 0; }