2013-team4/code/blossom

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
一般图匹配算法，时间复杂度O(N^3)
}}}
{{{
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=300;

vector<int> E[MAXN];
queue<int> q;
int map[MAXN][MAXN];
int next[MAXN], match[MAXN], fa[MAXN];
int mark[MAXN], vis[MAXN];
int N;

int getf(int x)
{
    if (x!=fa[x]) fa[x]=getf(fa[x]);
    return fa[x];
}

void Union(int a, int b)
{
    a=getf(a), b=getf(b);
    if (a!=b) fa[a]=b;
}

int LCA(int x, int y)
{
    static int t=0; t++;
    while (1)
    {
        if (x!=-1)
        {
            x=getf(x);
            if (vis[x]==t) return x;
            vis[x]=t;
            if (match[x]!=-1) x=next[match[x]];
            else x=-1;
        }
        swap(x, y);
    }
}

void group(int a, int p)
{
    while (a!=p)
    {
        int b=match[a], c=next[b];
        if (getf(c)!=p) next[c]=b;
        if (mark[b]==2) mark[b]=1, q.push(b);
        if (mark[c]==2) mark[c]=1, q.push(c);
        Union(a, b); Union(b, c); a=c;
    }
}

void findpath(int s)
{
    for (int i=0; i<N; i++) next[i]=-1, fa[i]=i, mark[i]=0, vis[i]=-1;
    while (!q.empty()) q.pop();
    q.push(s); mark[s]=1;
    while (match[s]==-1&&!q.empty())
    {
        int x=q.front(); q.pop();
        for (int i=0; i<(int)E[x].size(); i++)
        {
            int y=E[x][i];
            if (match[x]!=y&&getf(x)!=getf(y)&&mark[y]!=2)
            {
                if (mark[y]==1)
                {
                    int p=LCA(x, y);
                    if (getf(x)!=p) next[x]=y;
                    if (getf(y)!=p) next[y]=x;
                    group(x, p); group(y, p);
                }
                else if (match[y]==-1)
                {
                    next[y]=x;
                    for (int j=y; j!=-1;)
                    {
                        int k=next[j], l=match[k];
                        match[j]=k; match[k]=j;
                        j=l;
                    }
                    break;
                }
                else
                {
                    next[y]=x; q.push(match[y]);
                    mark[match[y]]=1; mark[y]=2;
                }
            }
        }
    }
}

int main()
{
    scanf("%d", &N);
    memset(map, 0, sizeof(map));
    int x, y;
    while (scanf("%d%d", &x, &y)!=EOF) map[x-1][y-1]=map[y-1][x-1]=1;
    for (int i=0; i<N; i++)
    {
        E[i].clear();
        for (int j=0; j<N; j++)
        {
            if (j==i||!map[i][j]) continue;
            E[i].push_back(j);
        }
    }
    memset(match, -1, sizeof(match));
    for (int i=0; i<N; i++) 
        if (match[i]==-1) findpath(i);
    int ret=0;
    for (int i=0; i<N; i++) if (match[i]!=-1) ret++;
    printf("%d\n", ret);
    for (int i=0; i<N; i++)
        if (match[i]!=-1&&match[i]>i) printf("%d %d\n", i+1, match[i]+1);
    return 0;
}
}}}

一般图匹配算法，时间复杂度O(N^3)

#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=300;
vector<int> E[MAXN];
queue<int> q;
int map[MAXN][MAXN];
int next[MAXN], match[MAXN], fa[MAXN];
int mark[MAXN], vis[MAXN];
int N;
int getf(int x)
{
    if (x!=fa[x]) fa[x]=getf(fa[x]);
    return fa[x];
}
void Union(int a, int b)
{
    a=getf(a), b=getf(b);
    if (a!=b) fa[a]=b;
}
int LCA(int x, int y)
{
    static int t=0; t++;
    while (1)
    {
        if (x!=-1)
        {
            x=getf(x);
            if (vis[x]==t) return x;
            vis[x]=t;
            if (match[x]!=-1) x=next[match[x]];
            else x=-1;
        }
        swap(x, y);
    }
}
void group(int a, int p)
{
    while (a!=p)
    {
        int b=match[a], c=next[b];
        if (getf(c)!=p) next[c]=b;
        if (mark[b]==2) mark[b]=1, q.push(b);
        if (mark[c]==2) mark[c]=1, q.push(c);
        Union(a, b); Union(b, c); a=c;
    }
}
void findpath(int s)
{
    for (int i=0; i<N; i++) next[i]=-1, fa[i]=i, mark[i]=0, vis[i]=-1;
    while (!q.empty()) q.pop();
    q.push(s); mark[s]=1;
    while (match[s]==-1&&!q.empty())
    {
        int x=q.front(); q.pop();
        for (int i=0; i<(int)E[x].size(); i++)
        {
            int y=E[x][i];
            if (match[x]!=y&&getf(x)!=getf(y)&&mark[y]!=2)
            {
                if (mark[y]==1)
                {
                    int p=LCA(x, y);
                    if (getf(x)!=p) next[x]=y;
                    if (getf(y)!=p) next[y]=x;
                    group(x, p); group(y, p);
                }
                else if (match[y]==-1)
                {
                    next[y]=x;
                    for (int j=y; j!=-1;)
                    {
                        int k=next[j], l=match[k];
                        match[j]=k; match[k]=j;
                        j=l;
                    }
                    break;
                }
                else
                {
                    next[y]=x; q.push(match[y]);
                    mark[match[y]]=1; mark[y]=2;
                }
            }
        }
    }
}
int main()
{
    scanf("%d", &N);
    memset(map, 0, sizeof(map));
    int x, y;
    while (scanf("%d%d", &x, &y)!=EOF) map[x-1][y-1]=map[y-1][x-1]=1;
    for (int i=0; i<N; i++)
    {
        E[i].clear();
        for (int j=0; j<N; j++)
        {
            if (j==i||!map[i][j]) continue;
            E[i].push_back(j);
        }
    }
    memset(match, -1, sizeof(match));
    for (int i=0; i<N; i++) 
        if (match[i]==-1) findpath(i);
    int ret=0;
    for (int i=0; i<N; i++) if (match[i]!=-1) ret++;
    printf("%d\n", ret);
    for (int i=0; i<N; i++)
        if (match[i]!=-1&&match[i]>i) printf("%d %d\n", i+1, match[i]+1);
    return 0;
}