【筆記】二分圖的最大匹配

  • 【範例】TIOJ 1089 . Asteroids
  • 用 DFS 找二分圖的最大匹配數目
    • g[xi][yj]:1 表示 xi 和 yj 之間可連通,反之為 0。
    • a[yj] = xi:表示把 yj 配對給 xi。
    • vis[yj]:表示 yj 已經被拜訪過。檢查每個新的 x 前都要先初始化 vis[ ] (Line-27)。
  • 枚舉 x
    • dfs (x):枚舉 y,進行匹配。
    • (Line-11) 如果找到一個 y (= i) 是未曾與別的 x 配對 (a[i] = 0),則可以把 x 配對給 i (a[i] = x)。
    • (Line-11) 如果 y (= i) 曾經與別的 x 配對 (a[i] != 0),則試試看能不能改變該 x 的配對方式,dfs (a[i])。成功改配的話,還是可以把 x 配對給 i (a[i] = x)。
  • 【圖例】
    • dfs (x1):a[y2] = x1, vis[y2] = 1
    • dfs (x2):a[y3] = x2, vis[y3] = 1
    • dfs (x3):a[y1] = x3, vis[y1] = 1
    • dfs (x4):a[y1] != 0 –> dfs (a[y1] = x3) –> (此時 vis[1] = vis[2] = vis[3] = 1) a[y4] = x1, a[y1] = x4
#include <iostream>
#include <cstring>
using namespace std;

int n, k, r, c, g[505][505], a[505], vis[505], ans;

bool dfs(int x){
    for (int i = 1; i <= n; i++){
        if (g[x][i] == 1 && vis[i]==0){
            vis[i] = 1;
            if (a[i]==0 || dfs(a[i])){
                a[i] = x;
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < k; i++){
        cin >> r >> c;
        g[r][c] = 1;
    }
    for (int i = 1; i <= n; i++){
        memset(vis, 0, sizeof(vis));
        if (dfs(i)) ans++;
    }
    cout << ans << "\n";
}
分享本文 Share with friends