UVA 車染色問題：二分圖多次完美匹配

題目大意

• N×N 棋盤上有若干車（Rook）。
• 需用最少顏色給車染色，使同行/同列的車顏色不同。
• 輸出最少顏色數及一種染色方案。

關鍵觀察

• 最少顏色數 = 任意行/列中車的最大數 K（由鴿巢原理）。
• 構造二分圖：左部 = 行，右部 = 列，每車對應一條邊 (r, c)。
• 需將邊分解為 K 個完美匹配（每匹配對應一種顏色）。
• 為保證每次完美匹配存在，補充虛擬邊使每行每列度數均為 K。

算法流程

1. 統計各行各列車數，得 K。
2. 建圖：車邊 + 補充虛擬邊（任意連接度數不足的行列）。
3. 重複 K 次：
    跑匈牙利算法求完美匹配。
    對匹配中屬於真實車的邊，賦予當前顏色。
    從圖中刪除該匹配的所有邊（真實+虛擬）。

完整代碼

#include 
using namespace std;
const int MAXN = 110;
int N, K;
vector G[MAXN];
int linkR[MAXN], rowDeg[MAXN], colDeg[MAXN];
char board[MAXN][MAXN];
int color[MAXN][MAXN];
bool vis[MAXN];

bool dfs(int u) {
    for (int v : G[u]) if (!vis[v]) {
        vis[v] = true;
        if (linkR[v] == -1 || dfs(linkR[v])) {
            linkR[v] = u;
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        cin >> N;
        for (int i = 0; i < N; ++i) {
            G[i].clear();
            rowDeg[i] = colDeg[i] = 0;
        }
        for (int i = 0; i < N; ++i) {
            cin >> board[i];
            for (int j = 0; j < N; ++j)
                if (board[i][j] == '*') {
                    G[i].push_back(j);
                    ++rowDeg[i]; ++colDeg[j];
                }
        }
        K = 0;
        for (int i = 0; i < N; ++i)
            K = max(K, max(rowDeg[i], colDeg[i]));
        // 補充虛擬邊
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N && rowDeg[i] < K; ++j)
                while (rowDeg[i] < K && colDeg[j] < K) {
                    G[i].push_back(j);
                    ++rowDeg[i]; ++colDeg[j];
                }
        memset(color, 0, sizeof(color));
        for (int c = 1; c <= K; ++c) {
            fill(linkR, linkR+N, -1);
            for (int i = 0; i < N; ++i) {
                fill(vis, vis+N, false);
                dfs(i);
            }
            // 分配顏色並刪除邊
            for (int j = 0; j < N; ++j) {
                int i = linkR[j];
                if (board[i][j] == '*') color[i][j] = c;
                // 從 G[i] 刪除 j
                auto it = find(G[i].begin(), G[i].end(), j);
                if (it != G[i].end()) G[i].erase(it);
            }
        }
        cout << K << "\n";
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (j) cout << ' ';
                cout << color[i][j];
            }
            cout << "\n";
        }
    }
    return 0;
}

複雜度

• 每次匹配 O(N·E)，E ≤ N·K。
• 共 K 次，總 O(K·N·E)，N ≤ 100 極快。