HDU 2435 There is a War：最小割與邊枚舉優化

問題描述

有向圖 N 個島嶼（節點），M 條橋（邊），每條邊有摧毀成本。國家 1（源點）攻擊國家 N（匯點），國家 N 想以最小總成本切斷所有 1→N 路徑。國家 1 可在戰前做一件事：新建一條不可摧毀的有向邊（端點在 2..N-1），或將現有邊升級為不可摧毀。求國家 1 能強迫國家 N 支付的最大可能最小摧毀成本。

核心洞察

• 原圖的最小割即為國家 N 不干預時的最小摧毀成本 ans0。
• 國家 1 的操作相當於將某條邊容量設為 INF（不可切割），再在殘量網絡上跑最大流，得到額外增加的流量 Δ。
• 枚舉所有原最小割中的邊（從 S 邊到 T 邊），將其容量設為 INF，在殘量圖上繼續增廣，記錄最大增量 maxΔ。
• 最終答案 = ans0 + maxΔ。

算法流程

1. 建圖，跑一次最大流（SAP/Dinic）得 ans0 並保存殘量網絡。
2. 根據最終層次圖劃分 S 集（從源點可達）與 T 集（其餘）。
3. 對每條滿足 u∈S, v∈T, cap>0 的原邊：臨時將容量設為 INF，在殘量圖上繼續跑最大流得增量，還原容量，取最大增量。
4. 輸出 ans0 + maxΔ。

關鍵代碼結構（SAP）

struct Edge { int to, next, cap, flow; };
vector<Edge> edges;
vector<int> head, cur, dep, gap, pre;

void addEdge(int u, int v, int w) {
    edges.push_back({v, head[u], w, 0});
    head[u] = edges.size() - 1;
    edges.push_back({u, head[v], 0, 0});
    head[v] = edges.size() - 1;
}

int sap(int s, int t, int n) {
    // 標準 SAP 實現，返回最大流
    // 並保留 dep, gap, cur, pre 等輔助數組以便後續增廣
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        init();
        for (int i=0;iedges[i].flow && !inS[v]){
                    inS[v]=1; q.push(v);
                }
            }
        }
        int maxAdd = 0;
        // 枚舉割邊
        for(int i=0;i0){
                int oldCap = edges[i].cap;
                edges[i].cap = INF;
                int add = sap(1, n, n);
                maxAdd = max(maxAdd, add);
                edges[i].cap = oldCap;
                // 還原流量狀態（或重新建圖更簡單）
            }
        }
        printf("%d\n", base + maxAdd);
    }
}

優化提示

• 枚舉時可直接重建圖，避免殘量網絡狀態回滾的複雜性。
• N ≤ 100，M ≤ 4950，重建圖 + 重跑流完全在時限內。