ACdream 1171 Matrix Sum（最大費用最大流與上下界轉化）

ACdream 1171 Matrix Sum - 最大費用最大流

這是一道經典的二分圖最大費用最大流問題，核心難點在於處理「至少選取」的下界約束。

題目大意

給定 N × M 矩陣，每個格子有一個非負整數權值。第 i 行至少要選 Ki 個數，第 j 列至少要選 Kj 個數。求滿足條件下被選數字之和的最小值。

核心轉化：下界轉上界

直接處理「至少選」的下界約束很麻煩，但可以巧妙轉化：

最小和 = 所有元素總和 - 最大可不選元素之和

具體轉化：

• 原問題：每行至少選 Ki 個 → 每行最多不選 (M - Ki) 個
• 原問題：每列至少選 Kj 個 → 每列最多不選 (N - Kj) 個
• 求「不選元素的最大和」→ 跑最大費用最大流
• 答案 = 總和 - 最大費用最大流結果

網絡流建模

• 源點 S 連向 N 個行節點，容量 = M - Ki，費用 = 0
• M 個列節點連向匯點 T，容量 = N - Kj，費用 = 0
• 行節點 i 連向列節點 j，容量 = 1，費用 = a[i][j]（矩陣元素值）
• 跑最大費用最大流，得到「不選元素的最大和」

關鍵代碼片段（SPFA 版最大費用流）

bool BellmanFord(int s, int t, LL &ans) {
    for (int i = 0; i <= t; i++) d[i] = -INF;  // 初始化為 -INF（求最大）
    memset(inq, 0, sizeof(inq));
    d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF;
    queue<int> Q; Q.push(s);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop(); inq[u] = 0;
        for (int i = 0; i < G[u].size(); i++) {
            Edge &e = edges[G[u][i]];
            if (e.cap > e.flow && d[e.to] < d[u] + e.cost) {  // 放寬條件：求最大
                d[e.to] = d[u] + e.cost;
                p[e.to] = G[u][i];
                a[e.to] = min(a[u], e.cap - e.flow);
                if (!inq[e.to]) { Q.push(e.to); inq[e.to] = 1; }
            }
        }
    }
    if (d[t] < 0) return false;  // 無增廣路或最大費用為負
    ans += (LL)d[t] * (LL)a[t];
    // 更新流量...
    return true;
}

與最小費用流的關鍵差異

複雜度與限制

• N, M ≤ 50，節點數 ≤ 102，邊數 ≤ 2500 + 100
• SPFA 最大費用流在這個規模下完全足夠
• T ≤ 40 組測試數據，總時間限制 8 秒

官方題解對比

官方題解使用鄰接表 + 手寫 SPFA，邏輯相同但代碼風格不同。兩份代碼核心思想一致：將有下界的費用流轉化為只有上界的普通費用流，這是解決此類問題的通用技巧。