HDU 2063 過山車：二分圖最大匹配（匈牙利算法）求最大配對數

問題建模

M 個女生（左部），N 個男生（右部），K 條可接受配對邊。
求最大匹配數，即最多多少對男女可同時坐上過山車（每排兩座位，一男一女）。

匈牙利算法核心流程

對每個左部節點 u，嘗試通過增廣路找到匹配：
1. DFS 從 u 出發，嘗試所有鄰接右節點 v。
2. 若 v 未被匹配，直接匹配 (u,v)。
3. 若 v 已匹配給 u'，嘗試為 u' 尋找新匹配（遞歸），成功則騰出 v 給 u。
4. 每輪 DFS 前重置訪問標記，避免重複搜索。
5. 總匹配數即為成功 DFS 次數。

完整 C++ 實作

#include 
#include 
#include 
using namespace std;

const int MAXN = 502;
int K, M, N;
int g[MAXN][MAXN];      // 鄰接矩陣
int matchR[MAXN];       // 右節點匹配的左節點
bool vis[MAXN];

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

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

int main() {
    while (scanf("%d", &K) == 1 && K) {
        scanf("%d%d", &M, &N);
        memset(g, 0, sizeof(g));
        for (int i = 0; i < K; ++i) {
            int u, v; scanf("%d%d", &u, &v);
            g[u][v] = 1;
        }
        printf("%d\n", hungarian());
    }
    return 0;
}

關鍵優化細節

• 鄰接矩陣 vs 鄰接表：M,N ≤ 500，矩陣 250KB 完全可行，訪問 O(1) 且代碼極簡。
• 訪問標記重置：每輪 DFS memset(vis, 0, ...)，避免時間戳優化（N=500 時 memset 極快）。
• 遞歸深度：最深 M ≤ 500，棧安全。
• 複雜度：O(M × E) = 500 × 1000 = 5×10⁵，極快。

替代解法：Hopcroft-Karp

O(√V × E) 理論更優，但 M,N=500 時匈牙利足夠且代碼簡潔得多。競程中除非 V>5000 否則首選匈牙利。

樣例驗證

Input:
6 3 3
1 1
1 2
1 3
2 1
2 3
3 1
0

Output:
3

女生 1,2,3 分別匹配男生 2,3,1（或任意完美匹配），共 3 對。