POJ 1962 Corporative Network：帶權并查集維護到根距離

問題建模

• N 個企業，初始各自為中心（根）。
• 操作 `I I J`：將中心 I 連接到企業 J，邊長 = |I−J| mod 1000。新叢集中心為 J 所在叢集的中心。
• 操作 `E I`：查詢企業 I 到其所在叢集中心的距離。

帶權并查集設計

維護 `fa[x]` = 父節點，`dist[x]` = x 到父節點的距離。
**查找**（路徑壓縮）：

int find(int x) {
    if (fa[x] == x) return x;
    int root = find(fa[x]);
    dist[x] += dist[fa[x]]; // 累加到根的距離
    return fa[x] = root;
}

**合併** `I I J`：

void unite(int I, int J) {
    int rootI = find(I), rootJ = find(J);
    if (rootI == rootJ) return;
    fa[rootI] = J;               // 將 I 的根掛到 J
    dist[rootI] = abs(I - J) % 1000; // 根到 J 的距離
}

注意：I 本身可能不是根，題目說「選擇現有中心 I」，故 I 應為根。但輸入保證 I 是中心？實際只需 `fa[I] = J; dist[I] = ...`，再 `find(I)` 更新即可。標準寫法如上。

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 20005;

int fa[MAXN], dist[MAXN];

int find(int x) {
    if (fa[x] == x) return x;
    int root = find(fa[x]);
    dist[x] += dist[fa[x]];
    return fa[x] = root;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int N; cin >> N;
        for (int i = 1; i <= N; ++i) {
            fa[i] = i;
            dist[i] = 0;
        }
        char op;
        while (cin >> op) {
            if (op == 'O') break;
            if (op == 'E') {
                int I; cin >> I;
                find(I);
                cout << dist[I] << '\n';
            } else { // 'I'
                int I, J; cin >> I >> J;
                int rootI = find(I);
                fa[rootI] = J;
                dist[rootI] = abs(I - J) % 1000;
            }
        }
    }
    return 0;
}

關鍵點

• 距離隨路徑壓縮自動累加，查詢時 `find` 後 `dist[I]` 即為到根距離。
• 合併時將整個叢集的根掛到 J，距離為 |I−J| mod 1000。
• 時間復雜度近似 O(α(N))，極快。