算法：帶花樹(shù)算法
問(wèn)題：一般圖的最大匹配問(wèn)題
輸入：簡(jiǎn)單無(wú)向圖
輸出：最大匹配的值、匹配方案
備注：一般圖的最大匹配問(wèn)題是NPC問(wèn)題

#include<bits/stdc++.h>
using namespace std;
enum { BLACK = 1, WHITE = 2 };

const int MAXN = 301;
const int MAXM = 1001;

int n;

struct Edge { int v, nxt; }e[MAXM];

int head[MAXN], tot, tim;
int mate[MAXN], stmp[MAXN];
int pre[MAXN], f[MAXN], clr[MAXN];
queue<int> que;

void init() {
    tot = tim = 0;
    memset(mate, 0, sizeof(mate));
    memset(stmp, 0, sizeof(stmp));
    memset(head, -1, sizeof(head));
}

int find(int x) {
    return f[x] == x ? f[x] : f[x] = find(f[x]);
}

void adde(int u, int v) {
    e[tot] = Edge{ v,head[u] };
    head[u] = tot++;
    e[tot] = Edge{ u,head[v] };
    head[v] = tot++;
}

int lca(int x, int y) {
    for (++tim;; swap(x, y)) if (x) {
        x = find(x);
        if (stmp[x] == tim)
            return x;
        else {
            stmp[x] = tim;
            x = pre[mate[x]];
        }
    }
}

void blossom(int x, int y, int p) {
    while (find(x) != p) {
        pre[x] = y;
        y = mate[x];
        if (clr[y] == WHITE)
            clr[y] = BLACK, que.push(y);
        if (find(x) == x)
            f[x] = p;
        if (find(y) == y)
            f[y] = p;
        x = pre[y];
    }
}

bool match(int s) {
    for (int i = 1; i <= n; i++) f[i] = i;
    while (!que.empty()) que.pop();
    memset(clr, 0, sizeof clr);
    memset(pre, 0, sizeof pre);
    clr[s] = BLACK, que.push(s);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int i = head[u]; ~i; i = e[i].nxt) {
            int v = e[i].v;
            if (find(v) == find(u) || clr[v] == WHITE) continue;
            if (!clr[v]) {
                clr[v] = WHITE;
                pre[v] = u;
                if (!mate[v]) {
                    for (; v; v = u) {
                        u = mate[pre[v]];
                        mate[pre[v]] = v;
                        mate[v] = pre[v];
                    }
                    return true;
                }
                clr[mate[v]] = BLACK, que.push(mate[v]);
            }
            else if (clr[v] == BLACK) {
                int p = lca(u, v);
                blossom(u, v, p);
                blossom(v, u, p);
            }
        }
    }
    return false;
}

int solve() {
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (!mate[i] && match(i))  ans++;
    return ans;
}