POJ 1719 最大匹配問題：匈牙利算法求解二分圖完美匹配

問題描述

給定一個二分圖，左側 n 個節點 (行)，右側 m 個節點 (列)。每列連接兩行。判斷是否存在從左到右的**完美匹配** (每行恰匹配一列，每列至多匹配一行)。若存在，輸出任意一組匹配方案；否則輸出 NO。多測試用例，SPJ 判題。

算法選型：匈牙利算法 (DFS 增廣路)

• 適用於無權二分圖最大匹配。
• 時間複雜度 O(V * E)，此處 n, m ≤ 1000，E = 2m，極快。
• 核心思想：對每個左節點嘗試 DFS 尋找增廣路，若目標右節點未被匹配或其原匹配左節點能騰出新匹配，則更新匹配關係。

關鍵代碼實現 (C++)

#include <cstdio>
#include <cstring>

const int MAXN = 1005;
bool g[MAXN][MAXN];     // 邊: 行 -> 列
bool used[MAXN];        // DFS 訪問標記 (列)
int link[MAXN];         // 列 -> 匹配的行 (-1 表示未匹配)
int n, m;

bool dfs(int u) {       // 為行 u 尋找匹配
    for (int v = 1; v <= m; ++v) {
        if (g[u][v] && !used[v]) {
            used[v] = true;
            if (link[v] == -1 || dfs(link[v])) { // 未匹配 或 原匹配行能騰位置
                link[v] = u;
                return true;
            }
        }
    }
    return false;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        memset(g, 0, sizeof(g));
        memset(link, -1, sizeof(link));

        if (n > m) { puts("NO"); continue; } // 必要條件

        // 輸入: 每列給出連接的兩行 x, y
        for (int i = 1; i <= m; ++i) {
            int x, y; scanf("%d%d", &x, &y);
            g[x][i] = g[y][i] = true;
        }

        int matchCnt = 0;
        for (int i = 1; i <= n; ++i) {
            memset(used, 0, sizeof(used));
            if (dfs(i)) ++matchCnt;
        }

        if (matchCnt < n) {
            puts("NO");
            continue;
        }

        // 輸出匹配方案: 遍歷列 1..m，輸出其匹配的行
        // 若某列未被匹配 (link[i]==-1)，任選一條連接的邊輸出 (SPJ 允許)
        for (int i = 1; i <= m; ++i) {
            if (link[i] != -1) printf("%d ", link[i]);
            else {
                for (int j = 1; j <= n; ++j)
                    if (g[j][i]) { printf("%d ", j); break; }
            }
        }
        puts("");
    }
    return 0;
}

核心邏輯解析

1. 建圖：輸入給的是「列連接哪兩行」，需轉置為「行連接哪些列」的鄰接矩陣 g[row][col]。
2. 必要條件剪枝：若 n > m (行數 > 列數)，鴿巢原理直接無解。
3. DFS 增廣：used[] 防止單次 DFS 重複訪問同一列；link[] 記錄當前匹配狀態。
4. 輸出構造：完美匹配時 link[1..m] 覆蓋所有行。未匹配列 (多餘列) 任選一條邊輸出即可滿足 SPJ。

複雜度與優化

• 時間：O(n * m) ≈ 10⁶ 操作，16MS 通過。
• 空間：鄰接矩陣 1005*1005 bool ≈ 1MB，可接受。稀疏圖可改用鄰接表 (vector adj[MAXN]) 節省內存。
• 進階優化：Hopcroft-Karp 算法 O(sqrt(V) * E)，處理更大規模 (10⁵ 級) 更優。