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

題目大意

過山車每排兩座位，女生只願意和特定男生同坐。給定 K 對願意配對的關係，M 個女生，N 個男生。求最大匹配對數（即最多多少對能坐上過山車）。

匈牙利算法解法

建立二分圖：左側女生，右側男生，邊表示願意配對。對每個女生嘗試尋找增廣路徑，使用 vis[] 標記本次 DFS 訪問過的男生，match[] 記錄男生當前匹配的女生。若找到未匹配男生或其匹配女生能騰出位置，則匹配成功。

代碼實現

bool dfs(int girl) {
    for (int boy = 1; boy <= N; ++boy) {
        if (like[girl][boy] && !vis[boy]) {
            vis[boy] = true;
            if (match[boy] == 0 || dfs(match[boy])) {
                match[boy] = girl;
                return true;
            }
        }
    }
    return false;
}

int main() {
    int K, M, N;
    while (scanf("%d%d%d", &K, &M, &N), K) {
        memset(like, 0, sizeof(like));
        memset(match, 0, sizeof(match));
        for (int i = 0; i < K; ++i) {
            int g, b; scanf("%d%d", &g, &b);
            like[g][b] = 1;
        }
        int ans = 0;
        for (int g = 1; g <= M; ++g) {
            memset(vis, 0, sizeof(vis));
            if (dfs(g)) ++ans;
        }
        printf("%d\n", ans);
    }
}

複雜度

O(M * K)，M ≤ 500, K ≤ 1000，完全足夠。若圖稠密可用 Hopcroft-Karp O(√V E) 優化。