HDU 5045 Contest：最小費用最大流建模求解（網絡流視角）

網絡流建模

將 M 題分成 ceil(M/N) 輪，每輪 N 題（最後一輪可能不足）。每輪內 N 人各做一題，構成二分圖匹配：左側 N 人，右側本輪題目，邊權 = 該人做該題的正確概率。
求每輪的最大權完美匹配，即最小費用最大流（費用取負概率）。

圖構造

• 源點 S，匯點 T。
• 左側 N 個人節點，右側本輪題目節點（數量 ≤ N）。
• S → 人：容量 1，費用 0。
• 人 → 題：容量 1，費用 -P[person][question]。
• 題 → T：容量 1，費用 0。

SPFA 求最小費用流

每輪跑一次費用流，流量 = 本輪題目數。累加費用取負得期望和。
因 N ≤ 10，每輪節點 ≤ 22，邊 ≤ 110，SPFA 極快。

參考代碼片段

struct Edge { int u, v, cap, next; double cost; } e[MAXE];
int head[MAXV], cnt;
void addEdge(int u, int v, int cap, double cost) { ... }

double minCostMaxFlow(int s, int t, int needFlow) {
    double cost = 0;
    int flow = 0;
    while (flow < needFlow) {
        // SPFA 找最短增廣路
        // 更新殘量網絡
    }
    return cost;
}

int main() {
    // 讀入 T
    for (cas=1..T) {
        // 讀 n, m, P[][]
        double total = 0;
        for (int round = 0; round * n < m; ++round) {
            int qCnt = min(n, m - round*n);
            // 建圖：人 1..n，題 n+1..n+qCnt
            // 加邊
            total += -minCostMaxFlow(S, T, qCnt);
        }
        printf("Case #%d: %.5lf\n", cas, total);
    }
}

關鍵點

• 每輪獨立建圖，因輪次間無約束（時間差 ≤ 1 已由分輪保證）。
• 費用取負概率，最小費用 = 最大期望。
• SPFA 需處理雙精度費用比較，用 d[v] > d[u] + cost 判斷鬆弛。
• 流量保證能滿（每輪題目數 ≤ 人數）。

複雜度

輪數 ≤ 1000/10 = 100。每輪 SPFA O(VE) ≈ 22*110 = 2420，總操作 < 3e5，極快。

總結

HDU 5045 除 DP 外，最小費用最大流是另一優雅解法：將每輪建模為二分圖最大權匹配。網絡流模板套用即可，代碼量稍大但思路清晰，適合擴展到更複雜約束（如每人每輪最多做幾題等）。