「笔记」带花树

带花树用来解决一般图的最大匹配问题。
考虑不能直接增广的原因是存在奇环。
带花树的思路是把奇环给缩成一朵花。
然后仍然通过增广路算法实现扩大匹配数目。
其中能缩成一朵花的原因是。
一堆点缩成花之后能够成为增广路中的某一个点，那么原图也可以。
这样就简化了模型从而可以直接用\(bfs\)增广。

1.uoj79
模板题
存个板子

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
inline void read(int &x)
{
    x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48,c=getchar();
}
const int maxn=505,maxm=maxn*maxn;
int ans,n,m,tot,dex,first[maxn],mt[maxn],id[maxn],pre[maxn],yet[maxn],fat[maxn];
queue<int> q;
struct Road{
    int u,t,nxt;
}eage[maxm<<1];
void add(int x,int y) {eage[++tot]=(Road){x,y,first[x]};first[x]=tot;}
void link(int x,int y) {add(x,y);add(y,x);}
int find(int x) {return fat[x]==x?x:fat[x]=find(fat[x]);}
int LCA(int x,int y)
{
    ++dex;x=find(x);y=find(y);
    for(;;swap(x,y))
        if(x)
        {
            if(yet[x]==dex) return x;
            yet[x]=dex;x=find(pre[mt[x]]);
        }
}
void bloss(int x,int y,int lca)
{
    while(find(x)!=lca)
    {
        pre[x]=y;
        if(id[mt[x]]) id[mt[x]]=0,q.push(mt[x]);
        if(fat[x]==x) fat[x]=lca;
        if(fat[mt[x]]==mt[x]) fat[mt[x]]=lca;
        y=mt[x];x=pre[y];
    }
}
int bfs(int S)
{
    for(int i=1;i<=n;++i) fat[i]=i,id[i]=-1,pre[i]=0;
    while(!q.empty()) q.pop();
    id[S]=0;q.push(S);
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=first[x],t;i;i=eage[i].nxt)
        {
            t=eage[i].t;
            if(id[t]==-1)
            {
                pre[t]=x;id[t]=1;
                if(!mt[t])
                {
                    for(int j=1;j;t=j,x=pre[j]) j=mt[x],mt[x]=t,mt[t]=x;
                    return 1;
                }
                id[mt[t]]=0;q.push(mt[t]);
            }
            else if(!id[t]&&find(x)!=find(t))
            {
                int lca=LCA(x,t);
                bloss(x,t,lca),bloss(t,x,lca);
            }
        }
    }
    return 0;
}
int main()
{
    read(n);read(m);
    for(int i=1,x,y;i<=m;++i) read(x),read(y),link(x,y);
    for(int i=1;i<=n;++i) if(!mt[i]) ans+=bfs(i);
    printf("%d\n",ans);
    for(int i=1;i<=n;++i) printf("%d ",mt[i]);
    return 0;
}

2.uoj171 挑战npc
说是npc是吓唬你的。
一个框里面放0或者1个点，对答案的贡献就是1，否则是0.
那么对每一个框拆成三个框。
三个框互相连边，球向三个框连边。
可以发现最终答案就是\(Max-n\)。
如果放入的是一个或0个球，这个框的匹配-球和框的匹配就是1，否则是0.
这样贡献就正确了。
同时先匹配球再匹配框。
防止框匹配上了球匹配不上。

「笔记」带花树

原文：https://www.cnblogs.com/Lrefrain/p/12354318.html