一般图最大匹配
带花树 一般图最大匹配    2017-01-14 13:58:11    232    0    0

 

类比二分图的匈牙利算法,思路还是从未配点开始,不断找交错路径

交错路径就是一条经过"未匹配边->已匹配边->未匹配边->已匹配边->……->未匹配边"的一条路径

为了方便,我们将到起始点距离为偶数的点称为偶点,否则为奇点(显然起始点是偶点)

显然增广路径满足"偶点->奇点->偶点->奇点->……->偶点"的顺序

 

二分图与一般图的最大区别就是一般图存在奇环

在奇环上的奇点,绕奇环一圈就变成了偶点

也就是说奇环上的点都可以看作是偶点

我们把奇环缩起来,然后做类似二分图的最大匹配就可以了

 

 

怎么缩奇环呢?

我们称奇环为"花"(blossom)

在搜索树上,当出现一条"偶点u<==>偶点v"的边(cross edge),就出现了一朵花

找到它们的"花托"(Base):LCA(u,v),然后把花上的奇点变成偶点

最后用并查集将花合并到一个集合里.


这个叫做带花树算法(blossoming)

找N次交错路径,时间复杂度O(NMα),其中α为并查集的时间复杂度

 

一个trick是边找交错路边缩花,减少代码量

 

#include <bits/stdc++.h>

inline void read(int &x)
{
    char c;
    while (!isdigit(c = getchar()));
    for  (x = 0; isdigit(c); c = getchar()) x = x * 10 + c - 48;
}

const int maxn = 500 + 5;
const int maxm = 250000 + 5;

int n, m;
int pre[maxn], next[maxn], fa[maxn], S[maxn], vis[maxn], *top, TIME;

int ans;

int st[maxm], cnte;
struct edge { int to, next; } e[maxm];

inline void addedge(int u, int v)
{
    e[++ cnte] = (edge) {v, st[u]}; st[u] = cnte;
}

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

int lca(int x, int y)
{
    ++ TIME;
    for (x = find(x), y = find(y); ; std::swap(x, y)) if (x) {
        if (vis[x] == TIME)
            return x;
        vis[x] = TIME;
        x = find(pre[next[x]]);
    }
}

void blossom(int x, int y, int lca)
{
    while (find(x) != lca) {
        pre[x] = y;
        if (S[next[x]] == 1) S[*top = next[x]] = 0, top ++; //odd vertex -> even vertex
        if (fa[x] == x) fa[x] = lca;
        if (fa[next[x]] == next[x]) fa[next[x]] = lca;
        y = next[x];
        x = pre[y];
    }
}

int match(int x)
{
    for (int i = 1; i <= n; i++)
        fa[i] = i;

    memset(S, -1, sizeof S);

    static int Q[maxn];

    S[x] = 0; 
    // 0 even vertex
    // 1 odd vertex
    top = &(Q[0] = x), top ++;

    for (int *i = Q; i != top; ++ i)
#define x (*i)
        for (int j = st[x]; j; j = e[j].next) {
            int y = e[j].to;
            if (S[y] == -1) {
                S[y] = 1; pre[y] = x;
                if (!next[y]) {
                    for (int u = y, v = x, lst; v; u = lst, v = pre[u])
                        lst = next[v], next[v] = u, next[u] = v;
                    // augmenting
                    return 1;
                }
                S[*top = next[y]] = 0, top ++;
            }
            else if (S[y] == 0 && find(y) != find(x)) { // find a blossom
                int Lca = lca(y, x);
                blossom(y, x, Lca);
                blossom(x, y, Lca);
            }
#undef x
        }

    return 0;
}

int main()
{
    read(n), read(m);
    for (int i = 1, x, y; i <= m; i++) {
        read(x);
        read(y);
        addedge(x, y);
        addedge(y, x);
    }

    for (int i = 1; i <= n; ++ i)
        if (!next[i]) 
            ans += match(i);

    printf("%d\n", ans);
    for (int i = 1; i <= n; ++ i)
        printf("%d ", next[i]);

    return 0;
}

 

参考了这个网站,详细的讲解:戳这里

仙人掌学习记录
232 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航