2018-team4-modules-一般图最大匹配

从 Trac 迁移的文章

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

原文章内容如下：

{{{
int fa[N],t,n,m;
bool g[N][N];
int gf(int x) { return fa[x] == x ? x : fa[x] = gf(fa[x]); }
void unit(int a,int b) { 
    a = gf(a) , b = gf(b);
    if (a != b) fa[a] = b;
}

int match[N];
vector<int> e[N];
int Q[N],rear;
int nex[N],mark[N],vis[N];

int LCA(int x,int y) {
    ++t;
    for (;;swap(x,y)) if (x){
        x = gf(x); 
        if (vis[x] == t) return x;
        vis[x] = t;
        x = nex[ match[x] ];
    }
}

void group(int a,int p) {
    while (a != p) {
        int b = match[a] , c = nex[b];
        if (gf(c) != p) nex[c] = b;
        if (mark[b] == 2) mark[Q[++rear] = b] = 1;
        //if (mark[c] == 2) mark[Q[++rear] = c] = 1;
        unit(a,b); unit(b,c);
        a = c; 
    }
}

void aug(int S) {
    for (int i=1;i<=n;i++) 
        nex[i] = mark[i] = vis[i] = 0;
    for (int i=1;i<=n;i++) fa[i] = i;
    mark[S] = 1; Q[1] = S; rear = 1;
    for (int head=1;/*!match[S] &&*/ head<=rear;head++) {
        int x = Q[head];
        for (int i=0;i<(int)e[x].size();i++) {
            int y = e[x][i];
            if (match[x] == y) continue;
            if (gf(x) == gf(y)) continue;
            if (mark[y] == 2) continue;
            if (mark[y] == 1) {
                int r = LCA(x,y);
                if (gf(x) != r) nex[x] = y;
                if (gf(y) != r) nex[y] = x;
                group(x,r); group(y,r);
            } else {
                if (match[y] == 0)  {
                    nex[y] = x;
                    for (int u=y;u;) {
                        int v = nex[u];
                        int mv = match[v];
                        match[u] = v; match[v] = u;
                        u = mv;
                    }
                    //break;
                    return;
                } else {
                    nex[y] = x;
                    mark[ Q[++rear] = match[y] ] = 1;
                    mark[y] = 2;
                }
            }
        }
    }

}
}}}

int fa[N],t,n,m;
bool g[N][N];
int gf(int x) { return fa[x] == x ? x : fa[x] = gf(fa[x]); }
void unit(int a,int b) { 
    a = gf(a) , b = gf(b);
    if (a != b) fa[a] = b;
}
int match[N];
vector<int> e[N];
int Q[N],rear;
int nex[N],mark[N],vis[N];
int LCA(int x,int y) {
    ++t;
    for (;;swap(x,y)) if (x){
        x = gf(x); 
        if (vis[x] == t) return x;
        vis[x] = t;
        x = nex[ match[x] ];
    }
}
void group(int a,int p) {
    while (a != p) {
        int b = match[a] , c = nex[b];
        if (gf(c) != p) nex[c] = b;
        if (mark[b] == 2) mark[Q[++rear] = b] = 1;
        //if (mark[c] == 2) mark[Q[++rear] = c] = 1;
        unit(a,b); unit(b,c);
        a = c; 
    }
}
void aug(int S) {
    for (int i=1;i<=n;i++) 
        nex[i] = mark[i] = vis[i] = 0;
    for (int i=1;i<=n;i++) fa[i] = i;
    mark[S] = 1; Q[1] = S; rear = 1;
    for (int head=1;/*!match[S] &&*/ head<=rear;head++) {
        int x = Q[head];
        for (int i=0;i<(int)e[x].size();i++) {
            int y = e[x][i];
            if (match[x] == y) continue;
            if (gf(x) == gf(y)) continue;
            if (mark[y] == 2) continue;
            if (mark[y] == 1) {
                int r = LCA(x,y);
                if (gf(x) != r) nex[x] = y;
                if (gf(y) != r) nex[y] = x;
                group(x,r); group(y,r);
            } else {
                if (match[y] == 0)  {
                    nex[y] = x;
                    for (int u=y;u;) {
                        int v = nex[u];
                        int mv = match[v];
                        match[u] = v; match[v] = u;
                        u = mv;
                    }
                    //break;
                    return;
                } else {
                    nex[y] = x;
                    mark[ Q[++rear] = match[y] ] = 1;
                    mark[y] = 2;
                }
            }
        }
    }
}