POJ 1274：最大二分匹配 (匈牙利算法 DFS 版)

問題描述

給定二分圖左側 n (≤200) 點，右側 m 點（隱含於邊中）。每行給出左側點連接的右側點列表。求最大匹配數。多測試案例，EOF 結束。

匈牙利算法 (DFS 增廣路)

對每個左側未匹配點 u，嘗試尋找增廣路：

• 遍歷 u 的鄰接點 v。
• 若 v 未訪問，標記訪問。
• 若 v 未匹配，或 v 的匹配點 match[v] 能找到新增廣路，則匹配 u-v，返回成功。

時間 O(V * E)，V≤200, E≤40000 極快。

參考代碼 (C++)

#include 
using namespace std;
const int MAXN = 205;
vector g[MAXN];
int matchR[MAXN], vis[MAXN], visToken;
int n, m;

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

int maxMatching() {
    fill(matchR, matchR + MAXN, -1);
    int ans = 0;
    for (int u = 1; u <= n; ++u) {
        ++visToken;
        if (dfs(u)) ++ans;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n >> m) {
        for (int i = 1; i <= n; ++i) g[i].clear();
        for (int i = 1; i <= n; ++i) {
            int cnt; cin >> cnt;
            while (cnt--) { int v; cin >> v; g[i].push_back(v); }
        }
        cout << maxMatching() << '\n';
    }
    return 0;
}

關鍵細節

• 訪問標記用 visToken 避免每次 memset，提速。
• 右側點編號可能不連續，但 matchR 數組開到最大可能值（200 足夠，題目右側點數 ≤ n）。
• 圖可能不連通，算法自動處理。

複雜度

O(n * E) ≈ 200 * 40000 = 8e6，C++ 瞬間通過。

總結

• 匈牙利算法是二分匹配入門必學，DFS 版代碼極短。
• 適用於稠密圖；稀疏圖可用 Hopcroft-Karp O(√V E) 但非必要。
• 模板化：dfs(u) 返回是否找到增廣路，matchR[v] 存儲匹配的左側點。