题目概述

UOJ79

解题报告

带花树板子题。由于一般图可以有奇环，所以不能直接匈牙利算法增广。

但是一个奇环中我们是可以调配使得只有一个点连向外部，因此奇环是可以当成一个单点看待的。

如果我们把奇环缩成“花”，然后就可以正常增广了。

详细过程可以看这篇博客，写的很好QwQ。

摘自上方博客：（ $i$ 点 $o$ 点可理解为黑点白点）

我们依次从每一个孤立点开始宽搜，并依次用 $i$ 与 $o$ 标记图上的点。

• 若寻找到一个未被标记的未匹配点：将其标记为 $i$ 型点，找到一条增广路，更新并维护该增广路的信息，完成增广。
• 若寻找到一个未被标记的点，但其已经被匹配，将其标记为 $i$ 型点，并将其匹配的点标记为 $o$ 型点，加入队列。
• 若寻找到一个已经被标记的 $i$ 型点，说明此时构成偶环，直接无视。
• 若寻找到一个已经被标记的 $o$ 型点，说明此时构成奇环且构成花，在当前扩展出的交错路上找到其公共祖先 $lca$ ，$lca$ 此时为花根，沿着两侧的花边爬到花根，将路径上的结点 $father$ 指针更新，标记全部更新为 $o$ ，并将 $pre$ 指针变为双向指针。

“花”的根节点一定是 $o$ 点，将“花”中所有点改为 $o$ 点，因为“花”中任意一个节点都可以认为是单点。

$pre$ 在链中代表BFS顺序的上一个节点，在“花”中 $pre$ 有双向指针，这样在找到增广路调整匹配时可以得知奇环的调整顺序。

复杂度好像是 $O(n^3+nm)$ ，不过跑不满，稀疏图跑得飞快。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=500,maxm=124750<<1;

int n,m,ans;
int E,lnk[maxn+5],nxt[maxm+5],son[maxm+5];
int who[maxn+5],pre[maxn+5],fa[maxn+5],tp[maxn+5];
int Head,Tail,que[maxn+5],ti,vis[maxn+5];

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
int LCA(int x,int y){
    x=fa[x];y=fa[y];
    for (ti++;vis[x]<ti;swap(x,y))
        if (x) vis[x]=ti,x=fa[pre[who[x]]];
    return x;
}
void Blossom(int x,int y,int lca){
    while (fa[x]!=lca){
        pre[x]=y;y=who[x];
        if (tp[y]) tp[y]^=1,que[++Tail]=y;
        fa[x]=fa[y]=lca;x=pre[y];
    }
}
bool Find(int x){
    for (int i=1;i<=n;i++) fa[i]=i,tp[i]=-1,pre[i]=0;
    Head=0;Tail=0;que[++Tail]=x;tp[x]=0;
    while (Head!=Tail){
        int x=que[++Head];
        for (int j=lnk[x],u;j;j=nxt[j])
            if (tp[u=son[j]]<0){
                tp[u]=1;pre[u]=x;
                if (!who[u]){
                    for (int p=u,lst;p;p=lst)
                        lst=who[pre[p]],who[p]=pre[p],who[pre[p]]=p;
                    return true;
                }
                tp[who[u]]=0;que[++Tail]=who[u];
            } else if (tp[u]==0){
                int lca=LCA(x,u);
                Blossom(x,u,lca);
                Blossom(u,x,lca);
            }
    }
    return false;
}
int main(){
    freopen("79.in","r",stdin);freopen("79.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x);
    for (int i=1;i<=n;i++) if (!who[i]) ans+=Find(i);
    printf("%d\n",ans);
    for (int i=1;i<=n;i++) printf("%d",who[i]),i<n?putchar(' '):puts("");
    return 0;
}