您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> 關於C語言

二分圖最大匹配：匈牙利算法原理、代碼模板與 POJ 實戰詳解

編輯：關於C語言

核心概念

二分圖

頂點集 V 可分為互不相交的兩子集 (A,B)，每條邊連接 A、B 中各一頂點。
二分圖示例

匹配與最大匹配

匹配：邊集中任意兩條邊無公共頂點
最大匹配：包含邊數最多的匹配

最小點覆蓋與 Kőnig 定理

點覆蓋：選擇最少頂點使所有邊至少有一端點被選中
定理：二分圖中最大匹配數 = 最小點覆蓋數

證明直觀：最大匹配 n 條邊需至少 n 個點覆蓋 → 最小點覆蓋 ≥ 最大匹配；最小點覆蓋中每點至少有一條邊唯一連接未覆蓋點 → 可構造同大小匹配 → 最大匹配 ≥ 最小點覆蓋。故相等。

匈牙利算法（深度優先增廣路）

核心思想

對 X 集合每個未匹配頂點，嘗試尋找增廣路（交替路，起點終點均為未匹配點），翻轉路徑上匹配/非匹配邊，匹配數 +1。

過程演示

初始無匹配
x1 匹配 y1
x2 匹配 y2
x3 嘗試 y1 已匹配 → 尋找增廣路 x3-y1-x1-y4 → 翻轉獲 x3-y1, x1-y4
依次加入 x4, x5

深度優先匈牙利算法模板

#define MAXN 505
int nx, ny;                    // X/Y 集合頂點數
int edge[MAXN][MAXN];          // 邊關係：edge[u][v]=1 表示可匹配
int cx[MAXN], cy[MAXN];        // 匹配結果：cx[u]=v, cy[v]=u
int visited[MAXN];             // 訪問標記

// 從 u 尋找增廣路
int path(int u) {
    for (int v = 0; v < ny; v++) {
        if (edge[u][v] && !visited[v]) {
            visited[v] = 1;
            if (cy[v] == -1 || path(cy[v])) {  // v 未匹配 或 v 的匹配點能騰位置
                cx[u] = v;
                cy[v] = u;
                return 1;
            }
        }
    }
    return 0;
}

// 最大匹配主函數
int maxmatch() {
    int res = 0;
    memset(cx, -1, sizeof(cx));
    memset(cy, -1, sizeof(cy));
    for (int i = 0; i < nx; i++) {
        if (cx[i] == -1) {
            memset(visited, 0, sizeof(visited));
            res += path(i);
        }
    }
    return res;
}

POJ 3041 實戰：Asteroids（最小點覆蓋）

題意：N×N 網格有 K 個障礙，一顆子彈消除一行或一列，求最少子彈數。
建模：行→X集合，列→Y集合，障礙→邊。最少子彈 = 最小點覆蓋 = 最大匹配。

#include <iostream>
#include <cstring>
using namespace std;

#define MAXN 505
int a[MAXN][MAXN], match[MAXN], vis[MAXN];
int N, K;

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

int main() {
    while (cin >> N >> K) {
        memset(a, 0, sizeof(a));
        memset(match, -1, sizeof(match));
        for (int i = 0; i < K; i++) {
            int r, c; cin >> r >> c;
            a[r][c] = 1;
        }
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            memset(vis, 0, sizeof(vis));
            if (dfs(i)) ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

POJ 3020 實戰：Ant Counting（網格最大獨立集）

關鍵建模：將每個 '*' 格點視為頂點，上下左右相鄰格點連邊 → 二分圖（按 (i+j)%2 染色）。
結論：最大獨立集 = 總點數 - 最大匹配/2（每條匹配邊消耗 2 個點）。

// 關鍵構圖邏輯
int init(int h, int w) {
    int ctr = 0;
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            if (str[i][j] == '*') {
                ctr++;
                int s = (i-1)*w + j;
                // 四方向連邊
                if (j+1<=w && str[i][j+1]=='*') a[s][(i-1)*w+j+1] = 1;
                if (i+1<=h && str[i+1][j]=='*') a[s][i*w+j] = 1;
                if (j-1>=1 && str[i][j-1]=='*') a[s][(i-1)*w+j-1] = 1;
                if (i-1>=1 && str[i-1][j]=='*') a[s][(i-2)*w+j] = 1;
            }
    return ctr;
}

// 主程序
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        memset(a, 0, sizeof(a));
        memset(match, -1, sizeof(match));
        int h, w; scanf("%d%d", &h, &w);
        // 讀網格...
        int total = init(h, w);
        N = h*w;
        int matchnum = 0;
        for (int i = 1; i <= N; i++) {
            memset(vis, 0, sizeof(vis));
            if (dfs(i)) matchnum++;
        }
        printf("%d\n", total - matchnum/2);
    }
}