HDU 2647 Reward：拓撲排序求最小獎金總和

題目大意

工廠老闆要給 n 名員工發年終獎，每人至少 888 元。另有 m 個需求 (a, b) 表示 a 的獎金必須多於 b。求滿足所有條件下的最小總獎金，若條件衝突（存在環）輸出 -1。

模型轉化

將每個需求 (a, b) 視為有向邊 b → a（b 的獎金少於 a）。這構成一個有向圖。若圖中有環，則無法滿足所有條件，輸出 -1。否則進行拓撲排序，每個節點的獎金 = 888 + 其入度為 0 的前驅節點數（即比它獎金少的人數）。

算法流程

1. 建圖：鄰接表存儲邊 b → a，並統計每個節點的入度。
2. 拓撲排序（Kahn 算法）：
   • 將入度為 0 的節點入隊，其獎金設為 888。
   • 每次取出隊首 u，遍歷其出邊 u→v，將 v 的入度減 1；若入度變 0，v 入隊，獎金 = 888 + 當前層級（或累積前驅計數）。
   • 實際上可維護一個 level[v] 表示 v 之前有多少個節點必須比它小，則獎金 = 888 + level[v]。
3. 若最終處理節點數 < n，說明有環，輸出 -1；否則累加所有獎金輸出。

關鍵代碼實現（靜態鄰接表版）

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int MAXV = 10005;
const int MAXE = 20005;

struct Edge { int to, next; } edges[MAXE];
int head[MAXV], indeg[MAXV], level[MAXV];
int n, m, ecnt;

void addEdge(int u, int v) {
    edges[ecnt] = {v, head[u]};
    head[u] = ecnt++;
    indeg[v]++;
}

bool topoSort(long long &total) {
    queue<int> q;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0) {
            q.push(i);
            level[i] = 0;
        }
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cnt++;
        total += 888 + level[u];
        for (int e = head[u]; e != -1; e = edges[e].next) {
            int v = edges[e].to;
            if (--indeg[v] == 0) {
                q.push(v);
                level[v] = level[u] + 1; // 也可累加前驅數
            }
        }
    }
    return cnt == n;
}

int main() {
    while (scanf("%d%d", &n, &m) == 2) {
        memset(head, -1, sizeof(head));
        memset(indeg, 0, sizeof(indeg));
        memset(level, 0, sizeof(level));
        ecnt = 0;
        for (int i = 0; i < m; i++) {
            int a, b; scanf("%d%d", &a, &b);
            addEdge(b, a); // b -> a
        }
        long long ans = 0;
        if (topoSort(ans)) printf("%lld\n", ans);
        else puts("-1");
    }
    return 0;
}

複雜度與注意點

• 時間 O(n+m)，空間 O(n+m)，滿足 n≤10000, m≤20000。
• 獎金總和可能超過 32 位整數，需用 long long。
• 輸入可能有多組測試數據，直到 EOF。

總結

本題是拓撲排序的經典應用：將不等式約束轉化為有向圖，檢測環並計算最小可行值。關鍵在於理解「比某人獎金少的人數」即為其在拓撲序中的層級，從而直接得到最小獎金分配方案。