HDU 2647 Reward（拓撲排序求最小工資總和）

HDU 2647 Reward - 拓撲排序應用

這道題將拓撲排序與最小化總和結合，是圖論在實際建模中的經典應用。

題目大意

N 個工人，M 個工資約束關係（a 的工資 > b 的工資）。每人工資至少 888。求滿足所有約束的最小工資總和。若存在衝突（環），輸出 -1。

建模分析

• 構建有向圖：邊 b → a 表示 a 的工資比 b 多
• 入度為 0 的點無前驅約束，工資設為基礎值 888
• 按拓撲序層層遞推：每層工資 = 上層工資 + 1
• 若最終處理節點數 < N，說明有環，輸出 -1

為什麼這樣能得到最小總和？

拓撲排序保證了所有約束被滿足。將無約束節點設為最小值 888，每層只比上層多 1，這是滿足「嚴格大於」約束的最小增量。任何其他分配方案都會導致某些節點工資更大，總和更大。

完整代碼實現

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 10010;
int inDegree[MAXN];
vector<int> child[MAXN];

struct State {
    int reward, node;
    State(int r, int n) : reward(r), node(n) {}
};

int main() {
    ios::sync_with_stdio(false);
    int n, m;
    while (cin >> n >> m) {
        memset(inDegree, 0, sizeof(inDegree));
        for (int i = 0; i <= n; i++) child[i].clear();
        
        for (int i = 0; i < m; i++) {
            int a, b; cin >> a >> b;
            inDegree[a]++;        // a 有前驅
            child[b].push_back(a); // b -> a
        }
        
        queue<State> q;
        long long ans = 0;
        int cnt = 0;
        
        // 入度為 0 的節點，工資從 888 開始
        for (int i = 1; i <= n; i++)
            if (inDegree[i] == 0) {
                q.push(State(888, i));
                cnt++;
            }
        
        while (!q.empty()) {
            State cur = q.front(); q.pop();
            ans += cur.reward;
            
            for (int v : child[cur.node]) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    q.push(State(cur.reward + 1, v));
                    cnt++;
                }
            }
        }
        
        if (cnt == n) cout << ans << endl;
        else cout << -1 << endl;
    }
    return 0;
}

關鍵細節

• 邊的方向：a > b ⇒ b → a，因為 b 的工資決定 a 的下界
• 工資遞增：每層 +1 是滿足「嚴格大於」的最小增量
• 環檢測：cnt != N 表示有節點無法入隊，存在環
• 數據範圍：N ≤ 10000, M ≤ 20000，鄰接表 + BFS 完全足夠

複雜度分析

• 時間：O(N + M) - 標準拓撲排序複雜度
• 空間：O(N + M) - 圖存儲 + 隊列 + 入度數組

變體思考

若約束改為「a 的工資 ≥ b 的工資 + k」，則拓撲序 DP 公式改為：

reward[v] = max(reward[v], reward[u] + k);

這就是經典的差分約束系統求最長路問題，可用 SPFA 解決。