HDU 4265 Science!：二分答案 + 最大流分解完美匹配

問題模型

n 人 n 個按鈕，Y/N 矩陣表示人能否站按鈕。每輪所有人各站一個不同按鈕，且同一人不能在不同輪次站同一按鈕。求最大輪數 k 並輸出 k 組完美匹配。n ≤ 80。

二分答案 + 最大流判定可行性

構建流網絡：源點 → 每人（容量 k）→ 每按鈕（容量 1，若允許）→ 匯點（容量 k）。跑 Dinic 最大流，若流量 = n×k 則可行。二分 k 找最大值。

分解流為 k 個完美匹配

得到最大流後，刪除流量為 0 的邊。剩餘圖中每人度 = k，每按鈕度 = k。重複 k 次：
1. 在殘留圖跑一次二分圖最大匹配（匈牙利/DFS）
2. 輸出匹配作為第 i 輪方案
3. 刪除已用邊
由正則二分圖定理（k-regular bipartite graph 可分解為 k 個完美匹配），必能成功。

關鍵代碼結構

// Dinic 最大流判定 k 可行性
bool check(int k) {
    Dinic D(2*n+2);
    for(i=1;i<=n;++i) { D.addEdge(S, i, k); D.addEdge(n+i, T, k); }
    for(i=1;i<=n;++i) for(j=1;j<=n;++j)
        if(can[i][j]) D.addEdge(i, n+j, 1);
    return D.maxflow(S,T) == n*k;
}

// 分解輸出
for(round=0; round<k; ++round) {
    Hungarian H(n);
    for(i=1;i<=n;++i) for(j=1;j<=n;++j) if(can[i][j]) H.addEdge(i,j);
    H.maxMatching(); // 得到 match[j]=i
    for(j=1;j<=n;++j) { print match[j]; can[match[j]][j]=false; }
}

複雜度

二分 log n 次 Dinic O(E√V) ≈ O(n².⁵)，分解 k 次匈牙利 O(k·n²) = O(n³)，n=80 完全足夠。