HDU 4687 Boke and Tsukkomi：一般圖最大匹配（帶花樹算法）

題目背景

比賽時誤以為是二分圖匹配，實際存在奇數環（如 1→2, 2→3, 3→1），必須使用一般圖最大匹配——帶花樹算法。

算法關鍵點

• 使用 BFS 尋找增廣路徑。
• 發現奇數環（花）時進行縮環，將環縮為一個新頂點。
• 維護 Base、Father、InQueue、InPath、InBlossom 等數組處理縮環與回溯。
• 最終通過 Edmonds 算法求最大匹配數。

完整代碼 (C++)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <map>
#include <list>
#include <cmath>
#include <set>
#include <queue>
using namespace std;

const int maxn = 55;
int n, m, Match[maxn], Head, Tail, Queue[maxn];
int Start, Finish, NewBase, Father[maxn], Base[maxn], cnt, Count;
bool InQueue[maxn], InPath[maxn], InBlossom[maxn], Graph[maxn][maxn];

void Push(int u) { Queue[Tail++] = u; InQueue[u] = true; }
int Pop() { return Queue[Head++]; }

int FindCommonAncestor(int u, int v) {
    memset(InPath, false, sizeof(InPath));
    while (true) {
        u = Base[u]; InPath[u] = true;
        if (u == Start) break;
        u = Father[Match[u]];
    }
    while (true) {
        v = Base[v];
        if (InPath[v]) break;
        v = Father[Match[v]];
    }
    return v;
}

void ResetTrace(int u) {
    int v;
    while (Base[u] != NewBase) {
        v = Match[u];
        InBlossom[Base[u]] = InBlossom[Base[v]] = true;
        u = Father[v];
        if (Base[u] != NewBase) Father[u] = v;
    }
}

void BlossomContract(int u, int v) {
    NewBase = FindCommonAncestor(u, v);
    memset(InBlossom, false, sizeof(InBlossom));
    ResetTrace(u); ResetTrace(v);
    if (Base[u] != NewBase) Father[u] = v;
    if (Base[v] != NewBase) Father[v] = u;
    for (int tu = 1; tu <= n; tu++)
        if (InBlossom[Base[tu]]) {
            Base[tu] = NewBase;
            if (!InQueue[tu]) Push(tu);
        }
}

void FindAugmentingPath() {
    memset(InQueue, false, sizeof(InQueue));
    memset(Father, 0, sizeof(Father));
    for (int i = 1; i <= n; i++) Base[i] = i;
    Head = Tail = 1; Push(Start); Finish = 0;
    while (Head < Tail) {
        int u = Pop();
        for (int v = 1; v <= n; v++)
            if (Graph[u][v] && Base[u] != Base[v] && Match[u] != v) {
                if (v == Start || (Match[v] > 0 && Father[Match[v]] > 0))
                    BlossomContract(u, v);
                else if (Father[v] == 0) {
                    Father[v] = u;
                    if (Match[v] > 0) Push(Match[v]);
                    else { Finish = v; return; }
                }
            }
    }
}

void AugmentPath() {
    int u = Finish, v, w;
    while (u > 0) {
        v = Father[u]; w = Match[v];
        Match[v] = u; Match[u] = v;
        u = w;
    }
}

void Edmonds() {
    memset(Match, 0, sizeof(Match));
    for (int u = 1; u <= n; u++)
        if (Match[u] == 0) {
            Start = u;
            FindAugmentingPath();
            if (Finish > 0) AugmentPath();
        }
}

int getMatch() {
    Edmonds();
    Count = 0;
    for (int u = 1; u <= n; u++) if (Match[u] > 0) Count++;
    return Count / 2;
}

// 以下為輸出匹配邊的輔助代碼（題目可能不需要）
struct node { int a, b; ... };
// 略