HDU 3061：Battle（戰鬥規劃——最大權閉合子圖 / 最小割）

問題：N 座城市，M 條拓撲依賴 (攻占 b 才能攻占 a)。每城有收益/損失值。選擇攻打子集最大化總收益，滿足依賴約束。

模型轉化

依賴關係構成有向圖 (a→b 表示 a 依賴 b)。選擇城市集合 S 需滿足：若 u∈S 且有邊 u→v，則 v∈S。即 S 為「閉合子圖」。權重為城市收益值（正為利，負為費）。求最大權閉合子圖。

最小割建圖

• 源點 S 連向正權節點，容量 = 正權值。
• 負權節點連向匯點 T，容量 = |負權值|。
• 依賴邊 u→v 加無限容量邊 u→v（選 u 必選 v）。

最大收益 = 總正權 - 最小割。用 SAP 最大流求解。

核心代碼 (SAP)

int sap(int s, int t, int N) {
    bfs(t); // 反向分層
    while (dep[s] < N) {
        if (u == t) { /* 增廣更新 */ }
        if (u != t && gap[dep[u]-1] == 0) break; // GAP 優化
        /* 當前弧優化尋找允許邊 */
        /* 回退重標號 */
    }
    return flow;
}

HDU 3061 是最大權閉合子圖的標準應用，與 HDU 3879 同模型。