本文主要是介绍POJ 2236 Wireless Network，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本题的关键点在与，给定一个修复好的u，谁是和它连通的呢？ 答案需要遍历全部的n，找出存在于并查集里的i，并且 距离（i, u） <= d。注意这里的u可能本来就已经修好，所以只需要find（i） == find（u） 就可以满足条件.
/************************************************ Author: fisty* Created Time: 2015/2/26 15:48:34* File Name : A.cpp*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
#define Memset(x, a) memset(x, a, sizeof(x))
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int, int> P;
#define FOR(i, a, b) for(int i = a;i < b; i++)
#define MAX_N 1010
int n, d;
int vis[MAX_N];
struct Point{int x;int y;
}p[MAX_N];
int dist(int i, int j){Point a = p[i];Point b = p[j];return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int par[MAX_N];
void init(){for(int i = 1;i <= n; i++){par[i] = i;}
}
int find(int x){if(x == par[x]) return x;return par[x] = find(par[x]);
}
void unio(int x, int y){x = find(x);y = find(y);par[x] = y;
}
int main() {//freopen("in.cpp", "r", stdin);//cin.tie(0);//ios::sync_with_stdio(false);cin >> n >> d;Memset(vis, 0);FOR(i, 1, n+1){cin >> p[i].x >> p[i].y;}init();char s[10];while(scanf("%s", s) != EOF){if(s[0] == 'O'){int u;cin >> u;if(!vis[u]){vis[u] = 1;int a = find(u);for(int i = 1;i <= n; i++){if(vis[i] && i != u && (find(i) == a || dist(i, u) <= d*d))unio(i, u);}}}else{int u, v;cin >> u >> v;if(vis[u] && vis[v]){if(find(u) == find(v)){cout << "SUCCESS" << endl;}else{cout << "FAIL" << endl;}}else cout << "FAIL" << endl;}}return 0;
}
这篇关于POJ 2236 Wireless Network的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
