您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

HDU 3038 How Many Answers Are Wrong：帶權並查集檢測矛盾

編輯：關於C++

題目大意

有 n 個變量，m 條約束 `x_a - x_b = w`（或等價的異或關係）。按順序處理約束，若新約束與已知矛盾，計數器 +1。輸出矛盾總數。

帶權並查集模型

`d[x]` = x 到其父節點的「距離/權值」（此處為差值）
路徑壓縮時累積權值：`d[x] += d[fa[x]]`
合併時根據已知關係計算新權值

核心代碼


const int MAXN = 200005;
int fa[MAXN], d[MAXN]; // d[x]: x 到 fa[x] 的差值 (x - fa[x])

int find(int x) {
    if (fa[x] == x) return x;
    int root = find(fa[x]);
    d[x] += d[fa[x]]; // 累積到根的差值
    return fa[x] = root;
}

// 返回 true 表示無矛盾，false 表示矛盾
bool unite(int a, int b, int w) { // 條件: a - b = w
    int ra = find(a), rb = find(b);
    if (ra == rb) {
        return (d[a] - d[b]) == w; // 已知關係檢查
    }
    // 合併: 使 ra 父為 rb
    fa[ra] = rb;
    // 要求: d[ra] = ra - rb
    // 已知: a - b = w
    //      a - ra = d[a]  => ra = a - d[a]
    //      b - rb = d[b]  => rb = b - d[b]
    // 所以: ra - rb = (a - d[a]) - (b - d[b]) = (a - b) - d[a] + d[b] = w - d[a] + d[b]
    d[ra] = w - d[a] + d[b];
    return true;
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        for (int i = 0; i <= n; ++i) { fa[i] = i; d[i] = 0; }
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            int a, b, w; cin >> a >> b >> w;
            if (!unite(a, b, w)) ++ans;
        }
        cout << ans << '\n';
    }
}