HDU 3315 My Brute：費用流建模與巧妙圖構造

題目大意

給定 n 個角色，每個角色有攻擊、血量、防禦屬性。需安排對戰順序使總得分最大化，且盡量保持原序號對戰。得分規則：贏得 +V_i，輸掉 -V_i。

費用流建模核心

構造二分圖：源點連左側 S_i（流量 1，費用 0），右側 X_j 連匯點（流量 1，費用 0）。若 S_i 能贏 X_j，連邊費用 -V[i]*1000；若 i == j 再減 1（優先保持原序）。輸的情況費用取正並同樣處理。最終 cost/1000 為最大得分，cost%1000 為改變順序的場數。

關鍵判斷函數

int pan(int x1, int x2, int y1, int y2) {
    while(1) {
        x2 -= y1; if (x2 <= 0) return 1;
        x1 -= y2; if (x1 <= 0) return 0;
    }
}

模擬雙方互毆，判斷 i 能否贏 j。

SPFA 求最小費用最大流

標準 SPFA 實現，注意費用縮放 1000 倍以分離主次目標。代碼結構清晰，包含加邊、最短路增廣、結果解析。

// 完整代碼見原文，核心為 mcmf() 與 main() 中的建圖邏輯
// 關鍵點：費用放大 1000 倍 + 同序號微調，確保字典序最優