HDU 3047 Zjnu Stadium：帶權並查集解決無限行距離矛盾檢測

HDU 3047 Zjnu Stadium：帶權並查集解決無限行距離矛盾檢測

題目大意：無限行矩陣中，每人佔一列。給定 m 條關係「a 與 b 相距 c 列」，檢測有多少條關係與前面矛盾。行數無限，故僅需考慮列距離。

核心洞察：帶權並查集維護相對距離

• 每個人屬於一個集合，集合內任意兩人距離關係已確定
• dist[x] 表示 x 到其根節點的距離（有向：x 到 root 為 +dist[x]）
• 合併時根據向量加法關係更新 dist

資料結構定義

const int MAXN = 50010;
int fa[MAXN];      // 父節點
int dist[MAXN];    // 到父節點的距離（路徑壓縮後為到根距離）

初始化

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

尋找根節點 + 路徑壓縮 + 距離維護

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

合併與矛盾檢測

// 關係：a 到 b 距離為 c (即 pos[b] - pos[a] = c)
bool unite(int a, int b, int c) {
    int ra = find(a), rb = find(b);
    if (ra == rb) {
        // 已在同一集合，檢查距離是否一致
        // dist[a] = pos[a] - pos[ra], dist[b] = pos[b] - pos[rb]
        // pos[b] - pos[a] = (dist[b] + pos[rb]) - (dist[a] + pos[ra]) = dist[b] - dist[a]
        return (dist[b] - dist[a] == c);
    }
    // 合併：將 rb 掛到 ra 下
    fa[rb] = ra;
    // 需要設定 dist[rb] 使關係成立
    // pos[b] - pos[a] = c
    // (dist[b] + pos[rb]) - (dist[a] + pos[ra]) = c
    // pos[rb] - pos[ra] = c + dist[a] - dist[b]
    // dist[rb] = pos[rb] - pos[ra] = c + dist[a] - dist[b]
    dist[rb] = c + dist[a] - dist[b];
    return true;
}

完整代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 50010;
int T, n, m;
int fa[MAXN], dist[MAXN];

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

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

bool unite(int a, int b, int c) {
    int ra = find(a), rb = find(b);
    if (ra == rb) {
        return (dist[b] - dist[a] == c);
    }
    fa[rb] = ra;
    dist[rb] = c + dist[a] - dist[b];
    return true;
}

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

向量關係圖解驗證

合併前：           合併後：
a --dist[a]--> ra          a --dist[a]--> ra
b --dist[b]--> rb    →     b --dist[b]--> rb --dist[rb]--> ra
已知：pos[b] - pos[a] = c
推導：dist[rb] = c + dist[a] - dist[b]

複雜度分析

• 時間：O(m α(n))，α 為反阿克曼函數，近似常數
• 空間：O(n)

關鍵點總結

1. 無限行 → 僅考慮列距離，轉化為一維相對位置問題
2. 帶權並查集 → 維護節點到根的有向距離
3. 路徑壓縮時累加距離 → dist[x] += dist[fa[x]]
4. 合併時向量加法 → dist[rb] = c + dist[a] - dist[b]
5. 矛盾判定 → 同集合下 dist[b] - dist[a] != c

此題是帶權並查集的標準應用，掌握「距離定義、壓縮累加、合併向量關係」三大核心操作即可舉一反三解決類似相對關係維護問題。