HDU 1281 棋盤遊戲 解題報告：二分圖最大匹配 + 關鍵邊判定

題目大意

n×m 棋盤，k 個可放棋子的格子。棋子攻擊規則：同行或同列。求：

1. 最大能放多少棋子（不互相攻擊）
2. 有多少個「關鍵格子」——移除後最大匹配數減少

建模：二分圖最大匹配

• 左部：行 1..n
• 右部：列 1..m
• 邊：可放棋子的格子 (r,c) 對應邊 r→c
• 最大匹配數 = 最大放置棋子數

匈牙利算法模板

bool dfs(int u) {
    for (int v = 1; v <= m; v++) {
        if (!vis[v] && g[u][v]) {
            vis[v] = true;
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int hungarian() {
    memset(match, -1, sizeof(match));
    int ans = 0;
    for (int u = 1; u <= n; u++) {
        memset(vis, 0, sizeof(vis));
        if (dfs(u)) ans++;
    }
    return ans;
}

關鍵邊判定

一條邊 (u,v) 是關鍵邊 ⟺ 它屬於**所有**最大匹配。
等價判定：刪除該邊後重新跑最大匹配，若匹配數減少 → 關鍵邊。

複雜度：O(k * n * m)，n,m ≤ 100, k ≤ n*m 可接受。

完整程式碼

#include 
using namespace std;

const int MAXN = 105;
bool g[MAXN][MAXN];
int match[MAXN], vis[MAXN];
int n, m, k;

bool dfs(int u) {
    for (int v = 1; v <= m; v++) {
        if (!vis[v] && g[u][v]) {
            vis[v] = true;
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int hungarian() {
    memset(match, -1, sizeof(match));
    int ans = 0;
    for (int u = 1; u <= n; u++) {
        memset(vis, 0, sizeof(vis));
        if (dfs(u)) ans++;
    }
    return ans;
}

struct Edge { int r, c; } edges[10005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int caseNo = 0;
    while (cin >> n >> m >> k) {
        memset(g, 0, sizeof(g));
        for (int i = 0; i < k; i++) {
            cin >> edges[i].r >> edges[i].c;
            g[edges[i].r][edges[i].c] = true;
        }

        int maxMatch = hungarian();
        int critical = 0;

        for (int i = 0; i < k; i++) {
            // 臨時刪除邊
            g[edges[i].r][edges[i].c] = false;
            int cur = hungarian();
            g[edges[i].r][edges[i].c] = true; // 恢復
            if (cur < maxMatch) critical++;
        }

        cout << "Board " << ++caseNo << " have " << critical
             << " important blanks for " << maxMatch << " chessmen.\n";
    }
    return 0;
}

優化方向（選做）

若 k 很大，可用以下方法判定關鍵邊 O(n*m) 總體：

1. 跑一次最大匹配，得到匹配邊集合 M
2. 構建殘留網絡：匹配邊反向、非匹配邊正向
3. 從未匹配的左部點出發 DFS，標記可達點
4. 從未匹配的右部點出發反向 DFS，標記可達點
5. 邊 (u,v) ∈ M 是關鍵邊 ⟺ u 可達且 v 可達（在殘留網絡中）

本題數據範圍較小，暴力刪邊重跑即可 AC。

複雜度

• 時間：O(k * n * m) ≤ 100 * 100 * 10000 = 10^8，實測 < 1s
• 空間：O(n*m)

易錯點

1. 多測試用例：每輪需清空圖、匹配、訪問陣列
2. 輸出格式：完全匹配樣例格式，包括句點
3. 邊刪除恢復：判定後必須恢復，否則影響後續判定

總結

經典「二分圖最大匹配 + 關鍵邊」模板題。核心步驟：

• 棋盤 → 二分圖（行/列）
• 匈牙利算法求最大匹配
• 枚舉邊刪除重跑判定關鍵性

掌握此模式，可解決「最小點覆蓋、最大獨立集、關鍵邊/點」等二分圖經典變體。