【題解】POJ 2236 Wireless Network

【題目敘述】https://vjudge.net/problem/POJ-2236
【解題想法】並查集,Disjoint Set Union-Find algorithm (DSU)

  • 兩台已經修復的電腦,如果其間的距離小於等於d,可以互相通訊。
  • v[i]:讀入測資時,順便計算這台電腦 (i) 與前面電腦間的距離,紀錄電腦 i 可連結的所有電腦。(Line-25)
  • p[i]:DSU,i 所屬集合的代表元素。初始值指向自己,p[i] = i。
  • fix[i]:紀錄電腦 i 的修復狀態。當修復電腦 i 時,順便將其與v[i]中「已經修復的」電腦進行並查集合併 (Union)。(Line-36)
  • 函式 Find( ):執行並查集的查詢功能。
  • 查詢兩台電腦能否通訊時,只要查詢兩台電腦所屬集合的代表元素是否相同即可。(Line-40)
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

int n, d, a, b;
int x[1005], y[1005], fix[1005], p[1005];
vector <int> v[1005];
char c;

int Find(int x){
    if (p[x] == x) return x;
    p[x] = Find(p[x]);
    return p[x];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> d;
    for (int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
        p[i] = i;
        for (int j = 1; j < i; j++){
            if ((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) <= d*d){
                v[i].push_back(j);
                v[j].push_back(i);
            }
        }
    }
    while (cin >> c){
        if (c == 'O'){
            cin >> a;
            fix[a] = 1;
            for (int i = 0; i < v[a].size(); i++){
                if (fix[v[a][i]] == 1) p[Find(v[a][i])] = Find(a);
            }
        } else {
            cin >> a >> b;
            if (Find(a) == Find(b)) cout << "SUCCESS\n";
            else cout << "FAIL\n";
        }
    }
    return 0;
}

分享本文 Share with friends