POJ 1719 Shooting Contest：二分匹配選白格子

問題描述

r 行 c 列矩陣，每列恰好兩個白格子。需每列選一個白格子，使每行至少被選一次。判斷是否可行，可行則輸出每列選擇的行號（多解任意）。

解題思路

建立二分圖：左側 c 列，右側 r 行。第 j 列連接其兩個白格子所在的行。求最大匹配，若匹配數 = r，則每行至少被覆蓋一次（因每列只能選一個，匹配邊即為選擇）。若 c > r，多餘列任意選一個白格子即可。輸出匹配結果，未匹配列取其任意白格子行。

代碼實現 (C++)

#include 
using namespace std;
const int MAXN = 1010;
vector G[MAXN];
int matchR[MAXN], matchC[MAXN], vis[MAXN], vstime;

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

int main() {
    int T; cin >> T;
    while (T--) {
        int r, c; cin >> r >> c;
        for (int i = 1; i <= c; ++i) G[i].clear();
        for (int j = 1; j <= c; ++j) {
            int a, b; cin >> a >> b;
            G[j].push_back(a);
            G[j].push_back(b);
        }
        fill(matchR, matchR+r+1, -1);
        fill(matchC, matchC+c+1, -1);
        int matchCnt = 0;
        for (int j = 1; j <= c; ++j) {
            ++vstime;
            if (dfs(j)) ++matchCnt;
        }
        if (matchCnt < r) {
            cout << "NO\n";
        } else {
            for (int j = 1; j <= c; ++j) {
                if (matchC[j] == -1) {
                    // 未匹配列，任選一個白格子
                    cout << G[j][0];
                } else {
                    cout << matchC[j];
                }
                if (j < c) cout << ' ';
            }
            cout << '\n';
        }
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(c * (r+c)) 匈牙利算法，r,c ≤ 1000 可接受。
• 空間複雜度：O(r+c)。

總結

二分匹配模板題，將「每行至少一次」轉化為「最大匹配覆蓋所有行」。注意 c > r 時多餘列任意選擇，輸出格式要求每列一個數字。