HDU 3047 ZJNU Stadium：並查集與距離追蹤解決座位衝突問題

問題背景

在 2007 年浙江大學生運動會中，浙江師範大學新建了一座現代化體育場，觀眾席呈圓形排列，共 300 列（順時針編號 1–300），行數視為無限。現在要安排 N 個人（編號 1–N）入座，並有 M 個需求，每個需求形式為 A B X，表示「編號 B 的人必須坐在編號 A 的人順時針 X 列處」。例如 A 在第 4 列、X=2，則 B 必須在第 6 列。需求按順序給出，若新需求與先前已接受的需求衝突，則判定為錯誤。任務是找出所有錯誤需求的總數 R。

核心觀察

• 座位列號對 300 取模，因此實際上是模 300 的循環群。
• 每個需求 A B X 等價於：pos[B] - pos[A] ≡ X (mod 300)，即 pos[B] ≡ pos[A] + X (mod 300)。
• 這是一個帶權的並查集問題：每個節點維護到其根節點的距離（模 300）。合併兩個集合時，利用向量關係計算新根的距離偏移。

演算法詳解

資料結構

int parent[MAXN];  // 父節點
int dist[MAXN];    // 到父節點的距離（模 300）

Find 操作（路徑壓縮 + 距離累加）

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

Merge 操作（向量加法原理）

已知 pos[B] - pos[A] = X (mod 300)。設 ra = find(A), rb = find(B)，且已知 dist[A] = pos[A] - pos[ra], dist[B] = pos[B] - pos[rb]。若 ra == rb，檢查 (dist[B] - dist[A] - X) % 300 == 0 是否成立；否則將 ra 掛在 rb 下，並設定 dist[ra] = (dist[B] - dist[A] - X) % 300（調整為非負）。

bool merge(int a, int b, int x) {
    int ra = find(a), rb = find(b);
    if (ra == rb) {
        return (dist[b] - dist[a] - x) % 300 == 0;
    }
    parent[ra] = rb;
    dist[ra] = (dist[b] - dist[a] - x) % 300;
    if (dist[ra] < 0) dist[ra] += 300;
    return true;
}

完整流程

1. 初始化：每個人各自為一個集合，parent[i]=i, dist[i]=0。
2. 依序讀取 M 個需求，調用 merge(A, B, X)。
3. 若回傳 false，計數器 R++。
4. 輸出 R。

複雜度分析

• 時間：近乎 O(M α(N))，α 為反阿克曼函數，極小。
• 空間：O(N)。

關鍵點總結

本題將「順時針距離」轉化為模 300 的差值約束，利用帶權並查集維護節點到根的相對位移。路徑壓縮時同步更新距離，合併時利用向量關係 pos[ra] = pos[rb] + (dist[B] - dist[A] - X) 計算新偏移。這是經典的「並查集維護模數差值」模板題。

參考程式碼 (C++)

#include <cstdio>
#include <cstring>
#define MAXN 50010

int parent[MAXN], dist[MAXN];

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

bool merge(int a, int b, int x) {
    int ra = find(a), rb = find(b);
    if (ra == rb) {
        return (dist[b] - dist[a] - x) % 300 == 0;
    }
    parent[ra] = rb;
    dist[ra] = (dist[b] - dist[a] - x) % 300;
    if (dist[ra] < 0) dist[ra] += 300;
    return true;
}

int main() {
    int N, M;
    while (scanf("%d%d", &N, &M) == 2) {
        for (int i = 1; i <= N; ++i) {
            parent[i] = i;
            dist[i] = 0;
        }
        int R = 0;
        for (int i = 0; i < M; ++i) {
            int A, B, X;
            scanf("%d%d%d", &A, &B, &X);
            if (!merge(A, B, X)) ++R;
        }
        printf("%d\n", R);
    }
    return 0;
}