HDU 3047 Zjnu Stadium 解題報告：帶權並查集

題目大意

有 n 個人站在無限長的走廊中（行數無限，只考慮列距離）。給出 m 條資訊：「人 a 與人 b 相距 c 列」。判斷有多少條資訊與前面資訊矛盾。

核心洞察

• 行數無限 ⇒ 兩人可在不同行但列距相同
• 矛盾只發生在：同一連通分量內，推導出的距離與給定距離不符
• 需維護「點到集合根節點的相對距離」→ 帶權並查集

帶權並查集設計

• p[x]：父節點
• dist[x]：節點 x 到其父節點的距離（有向，x 到 p[x] 為正）
• 路徑壓縮時累加距離：dist[x] += dist[fa]

關鍵操作

Find（路徑壓縮+距離更新）

int find(int x) {
    if (p[x] == x) return x;
    int fa = p[x];
    p[x] = find(p[x]);
    dist[x] += dist[fa];  // 累加到新父節點的距離
    return p[x];
}

Union / 矛盾檢測

bool unite(int a, int b, int c) {
    int x = find(a), y = find(b);
    if (x == y) {
        // 同集合：檢查 a 到 b 的距離是否為 c
        // dist[a] = a 到根距離, dist[b] = b 到根距離
        // a 到 b = dist[a] - dist[b] （向量減法）
        return (dist[a] - dist[b] == c);
    }
    // 合併：將 y 掛到 x 下，設置 dist[y] 使關係成立
    // 要求：dist[a] - (dist[b] + dist[y]) = c
    // 解得：dist[y] = dist[a] - dist[b] - c
    p[y] = x;
    dist[y] = dist[a] - dist[b] - c;
    return true;
}

完整程式碼

#include <cstdio>
#include <cstring>

const int maxn = 50000 + 10;
int p[maxn], dist[maxn];

void init(int n) {
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        dist[i] = 0;
    }
}

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

bool check(int a, int b, int c) {
    int x = find(a), y = find(b);
    if (x == y) {
        return (dist[a] - dist[b] == c);
    }
    p[y] = x;
    dist[y] = dist[a] - dist[b] - c;
    return true;
}

int main() {
    int n, m, a, b, c;
    while (~scanf("%d%d", &n, &m)) {
        init(n);
        int ans = 0;
        while (m--) {
            scanf("%d%d%d", &a, &b, &c);
            if (!check(a, b, c)) ++ans;
        }
        printf("%d\n", ans);
    }
    return 0;
}

向量關係圖解

根節點 x
  ↑ dist[a]
  a
  ↑ c (given a->b = c)
  b
  ↑ dist[b]
  根節點 y (合併前)
合併後 y 掛在 x 下，需設定 dist[y] 使向環一致

複雜度

• 時間：O(m α(n))，近似線性
• 空間：O(n)

易錯點

1. 距離方向一致性：統一約定「子節點到父節點為正」，推導公式時注意向量加減
2. 路徑壓縮時距離累加順序：必須先遞歸找到根，回溯時 dist[x] += dist[fa]
3. 合併公式推導：畫向量圖驗證 dist[y] = dist[a] - dist[b] - c

總結

帶權並查集是處理「動態等式系統/相對關係」的利器。本題關鍵在於識別「無限行」意味著只有列距離約束，轉化為一維帶權並查集模型。