HDU 1281 棋盤遊戲：二分圖最大匹配與關鍵邊判定

HDU 1281 棋盤遊戲：二分圖最大匹配與關鍵邊判定

問題建模

棋盤上有 k 個棋子，每個佔據一格 (r, c)。要放置最大數量的互不攻擊棋子（即同行同列最多一個），等價於二分圖最大匹配：
- 左側點集：行 1..n
- 右側點集：列 1..m
- 邊：有棋子的格子 (r, c) 連接行 r 和列 c。
最大匹配數即為最多能放置的棋子數。

關鍵邊判定

一條邊（棋子）若移除後最大匹配數變小，則稱該邊為「關鍵」（important blank）。對每條邊嘗試刪除，重跑匈牙利算法，若匹配數減少則計數器++。k ≤ 100×100，匈牙利 O(k×(n+m)) 足夠快。

匈牙利算法核心

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

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

完整代碼 (C++)

#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 110;
bool g[MAXN][MAXN];
int link[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] = 1;
            if (link[v] == -1 || dfs(link[v])) {
                link[v] = u;
                return true;
            }
        }
    return false;
}

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

struct Edge { int r, c; } e[MAXN*MAXN];

int main() {
    int tc = 0;
    while (scanf("%d%d%d", &n, &m, &k) == 3) {
        memset(g, 0, sizeof(g));
        for (int i = 0; i < k; i++) {
            scanf("%d%d", &e[i].r, &e[i].c);
            g[e[i].r][e[i].c] = true;
        }
        int init = hungarian();
        int important = 0;
        for (int i = 0; i < k; i++) {
            g[e[i].r][e[i].c] = false;
            if (hungarian() < init) important++;
            g[e[i].r][e[i].c] = true;
        }
        printf("Board %d have %d important blanks for %d chessmen.\n", ++tc, important, init);
    }
    return 0;
}

複雜度

• 單次匈牙利：O(n × k) ≈ 100 × 10000 = 10⁶。
• k 次嘗試：O(k × n × k) ≈ 10⁸，邊界較緊但 C++ 常數小通常能過。可優化：僅對初始匹配中的邊測試，或用 Tarjan 強連通分量判定關鍵邊（O(n+m)）。