HDU 1281：棋盤遊戲 - 二分圖最大匹配 (匈牙利算法) 及關鍵邊判定

問題描述

n×m 棋盤，部分格子可放車。車不可同行同列。求最大放車數 (最大匹配)，及有多少格子是「必須放車」才能達到最大匹配 (關鍵邊)。

建模：二分圖最大匹配

• 左部：行 (1..n)，右部：列 (1..m)。
• 可放車格子 (x,y) 連接行 x 和列 y。
• 匈牙利算法 (DFS 找增廣路) 求最大匹配 max_match。

關鍵邊判定 (兩種方法)

邊 (x,y) 在某個最大匹配中。判斷是否為關鍵邊 (即所有最大匹配都包含它)：

1. 暴力法：刪除該邊，重跑匈牙利，若最大匹配數減少則為關鍵邊。O(E * V*E)，小數據可過。
2. 增廣路法 (高效)：
   • 在一個最大匹配中，對匹配邊 (x,y)：刪除該邊，使 y 成為自由點。
   • 從 x 出發尋找增廣路。若找到，說明存在不含 (x,y) 的最大匹配，故非關鍵；若找不到，則為關鍵邊。
   • 檢查完須恢復原匹配。
   O(E * (V+E)) 總體更快。

代碼實現 (增廣路法)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;

bool g[MAXN][MAXN];
int matchR[MAXN]; // 列匹配的行
bool vis[MAXN];
int n, m;

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

int hungarian() {
    fill(matchR, matchR+m+1, -1);
    int cnt = 0;
    for (int u = 1; u <= n; ++u) {
        fill(vis, vis+m+1, false);
        if (dfs(u)) ++cnt;
    }
    return cnt;
}

int main() {
    int k, tc = 0;
    while (cin >> n >> m >> k) {
        memset(g, 0, sizeof(g));
        while (k--) { int x,y; cin>>x>>y; g[x][y]=true; }
        int max_match = hungarian();
        int critical = 0;
        // 記錄一個最大匹配的匹配邊
        vector> matched;
        for (int v = 1; v <= m; ++v)
            if (matchR[v] != -1) matched.emplace_back(matchR[v], v);

        for (auto [x,y] : matched) {
            g[x][y] = false;
            matchR[y] = -1;
            fill(vis, vis+m+1, false);
            if (!dfs(x)) ++critical; // 找不到增廣路 -> 關鍵邊
            g[x][y] = true;
            matchR[y] = x; // 恢復
        }
        cout << "Board " << ++tc << " have " << critical
             << " important blanks for " << max_match << " chessmen.\n";
    }
    return 0;
}

關鍵點

• 匈牙利算法模板：dfs 找增廣路，matchR 記錄右部匹配。
• 關鍵邊判定核心：刪除匹配邊後，原左端點能否找到新增廣路。
• 輸出格式固定：Board X have Y important blanks for Z chessmen.

總結

二分圖最大匹配 + 關鍵邊判定是經典組合。增廣路法避免了重複跑完整匈牙利，是判定「唯一匹配邊」的標準技巧。