POJ 3020 一般圖最大匹配：Edmonds 帶花算法（Blossom）

問題描述

給定 h×w 網格（h≤40, w≤10），每格為 '.'（空）或 '*'（需覆蓋）。用 1×2 矩形（多米諾骨牌）覆蓋所有 '*'，最少需要多少塊？矩形不可重疊，可覆蓋 '.'。

轉化為圖論模型

• 每個 '*' 為一個頂點。
• 相鄰（上下左右）兩個 '*' 連邊（可放一張多米諾）。
• 目標：選最少邊覆蓋所有頂點 → 最小邊覆蓋。
• 定理：最小邊覆蓋 = |V| - 最大匹配（對於無孤立點圖）。
• 本圖為一般圖（非二分），需 Edmonds 帶花算法 求最大匹配。

帶花算法核心思想

1. 從未匹配頂點發起 BFS 搜索增廣路。
2. 遇到奇環（花）時，將奇環縮為一個「超級頂點」，繼續搜索。
3. 找到增廣路後，沿路翻轉匹配/非匹配邊，匹配數 +1。
4. 重複直到無增廣路。

關鍵數據結構

• match[v]：v 匹配的頂點，-1 表示未匹配。
• base[v]：並查集代表元，縮花後所有頂點指向花的基點。
• p[v]：BFS 父節點（用於回溯增廣路）。
• q：BFS 隊列。
• in_blossom[v]、in_queue[v]、in_path[v] 等標記數組。

算法流程簡述

int lca(int u, int v) {  // 最近公共祖先
    static int t = 0; ++t;
    while (true) {
        if (u != -1) {
            u = base[u];
            if (in_path[u] == t) return u;
            in_path[u] = t;
            u = (match[u] == -1) ? -1 : p[match[u]];
        }
        swap(u, v);
    }
}

void mark_blossom(int u, int b, int child) {
    while (base[u] != b) {
        int v = match[u];
        in_blossom[base[u]] = in_blossom[base[v]] = true;
        p[u] = child; child = v;
        u = p[v];
    }
}

void blossom_contraction(int u, int v) {
    int b = lca(u, v);
    fill(in_blossom, in_blossom+N, false);
    mark_blossom(u, b, v);
    mark_blossom(v, b, u);
    for (int i = 0; i < N; ++i)
        if (in_blossom[base[i]]) {
            base[i] = b;
            if (!in_queue[i]) q.push(i), in_queue[i]=true;
        }
}

bool bfs(int root) {
    fill(p, p+N, -1);
    iota(base, base+N, 0);
    fill(in_queue, in_queue+N, false);
    q = queue(); q.push(root); in_queue[root]=true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (base[u]==base[v] || match[u]==v) continue;
            if (v==root || (match[v]!=-1 && p[match[v]]!=-1)) {
                blossom_contraction(u, v);
            } else if (p[v]==-1) {
                p[v] = u;
                if (match[v]==-1) {  // 找到增廣路
                    for (int cur=v; cur!=-1; ) {
                        int nxt = match[p[cur]];
                        match[cur] = p[cur];
                        match[p[cur]] = cur;
                        cur = nxt;
                    }
                    return true;
                } else {
                    q.push(match[v]);
                    in_queue[match[v]] = true;
                }
            }
        }
    }
    return false;
}

int edmonds() {
    fill(match, match+N, -1);
    int ans = 0;
    for (int i = 0; i < N; ++i)
        if (match[i]==-1 && bfs(i)) ++ans;
    return ans;
}

完整代碼框架（POJ 3020）

#include <bits/stdc++.h>
using namespace std;
const int MAXV = 405;  // 40*10
int h, w, id[45][15], V;
char grid[45][15];
vector adj[MAXV];
int match[MAXV], base[MAXV], p[MAXV], q[MAXV];
bool in_queue[MAXV], in_blossom[MAXV], in_path[MAXV];
int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1};

// ... 上述 lca, mark_blossom, blossom_contraction, bfs, edmonds ...

int main() {
    while (cin >> h >> w) {
        V = 0;
        for (int i=0;i> grid[i];
            for (int j=0;j=0&&ni=0&&nj

複雜度
Edmonds 算法 O(V^2 E) 或 O(V^3)，此處 V ≤ 400，E ≤ 4V，完全在 1s 內。POJ 3020 是帶花算法經典入門題。