说是有N个村庄，刚开始每个村庄的网络都是受损状态，于是派一个人去修理，修理过的村庄只能联系距离他们半径为D的村庄，当然他们可以通过一些村庄当中转站，联系。
输入先输入一个N表示有N个村庄，还有一个D表示每个村庄的最大通讯半径，接着有一系列的修复操作和查询操作，如果两个地方不通那么很明显应该输出FALL，否则SUCCESS。
题意已经很明确了，就是修复查询，修复好一个点后与其他修复后的点对比一下看看是否能连接成功。
/
时间用了3S，懒得优化了，优化方法可以搞一个数组转来保存已经修复的额点，这样判断起来少了很多冗余
#include<stdio.h> const int maxn = 1005; struct node { int x, y, ok; }p[maxn]; // 保存所有的村庄，ok表示是否已经修复 int f[maxn]; int Len(node a, node b) // 求两个村庄的距离 { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } int Find( int x) { if(f[x] != x) f[x] = Find(f[x]); return f[x]; } int main() { int i, N, D, u, v; char s[ 10]; scanf( " %d%d ", &N, &D); D = D*D; // 因为距离只做判断，所以直接用平方数判断更准确，避免小数 for(i= 1; i<=N; i++) { scanf( " %d%d ", &p[i].x, &p[i].y); p[i].ok = 0; f[i] = i; } while(scanf( " %s ", s) != EOF) { if(s[ 0] == ' O ') { scanf( " %d ", &u); if(p[u].ok == 0) { p[u].ok = 1; for(i= 1; i<=N; i++) { if(u != i && p[i].ok && Len(p[i], p[u]) <= D) { v = Find(i); int k = Find(u); f[k] = v; } } } } else { scanf( " %d%d ", &u, &v); u = Find(u); v = Find(v); if(u != v) printf( " FAIL\n "); else printf( " SUCCESS\n "); } } return 0;
}
重构了一下代码，试图弄出来并查集的模版，不过不是太理想
#includeconst int maxn = 1e3+7;struct FindSets{ int *Father, size; FindSets(int size) : size(size) { Father = new int[size+1]; for(int i=0; i<=size; i++) Father[i] = i; } ~FindSets() { delete[] Father; } int Find(int x) { if(Father[x] != x) Father[x] = Find(Father[x]); return Father[x]; } bool connect(int u, int v, bool need) { ///判断两个点是否相连,如果需要相连则连接 u = Find(u); v = Find(v); if(need == true) Father[v] = u; return u == v; }};struct point{ int x, y, fine;};bool Dis(point &a, point &b, int D){ ///判断两点之间的距离是否大于D return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)) <= D*D;}void Repair(int u, int D, point p[], FindSets &fs){ ///修复点u for(int i=1; i<=fs.size; i++) { if(p[i].fine == true && Dis(p[i], p[u], D)) fs.connect(i, u, true); } p[u].fine = true;}int main(){ int N, D; scanf("%d%d", &N, &D); FindSets fs(N); point *p = new point[N+1](); for(int i=1; i<=N; i++) scanf("%d%d", &p[i].x, &p[i].y); int u, v; char op[10]; while(scanf("%s", op) != EOF) { if(op[0] == 'O') { scanf("%d", &u); Repair(u, D, p, fs); } else { scanf("%d%d", &u, &v); if(fs.connect(u, v, false) == true) printf("SUCCESS\n"); else printf("FAIL\n"); } } delete[] p; return 0;}