刚了解很不熟练,有问题请及时指出 QAQ

带花树

带花树通常用于解决一般图最大匹配问题。

至于一般图最大权匹配问题,毒瘤请移步这里

考虑如何处理奇环,让环上的点两两匹配,总会剩下一个点,而且每一个环上的点都存在一种环上匹配方案使得该点被剩下,那么考虑将环缩成点,缩完的点一样可以匹配。

如果要支持输出方案,那么是不能实质缩点的,用并查集即可。

定义匹配的一对点分别为黑点和白点。

算法流程:

  • 从一个没有匹配出发,初始定义该点的颜色为黑。
    for(int i=1;i<=n;++i) if(!match[i]&&solve(i)) ++ans;
    
  • 每一次从队列里取出节点 $u$ 进行更新:
    • 如果相邻点 $v$ 在当前轮还没有被染色

    • 如果 $v$ 被匹配了

      那么将匹配拆散,$v$ 当前为白点,将其匹配的点染成黑点,并扔进队列继续匹配,如果 $v$ 的匹配点找到了合适的匹配,那么 $v$ 可以和当前的起点 $i$ 匹配,将多增加一组匹配。

      q.push(match[v]),col[match[v]]=1;
      
    • 如果 $v$ 没有匹配

      将 $v$ 匹配给起点 $i$ ,至于怎么维护可以每一个点记录 $pre$ ,然后暴力跳链更新:

      for(int las;u;v=las,u=pre[v])
        las=match[u],match[u]=v,match[v]=u;   
      return true;
      
    • 如果相邻点 $v$ 的颜色是白

    那么不用管,因为遇见了一个偶环。

    • 如果相邻点 $v$ 的颜色是黑

    • 如果 $v$ 和 $u$ 已经是同一个花里的了

      那么不用管。

    • 否则

      暴力开花,先找到 $lca$ ,显然花将包括 $u$ 到 $v$ 路径上的所有点 (花)。

      找到 $lca$ 后,分别从 $u$ 和 $v$ 开始往上面跳,并更新 $pre$ ,由于是花,花内的 $pre$ 一定是双向的,跳的时候还需要检查颜色,如果跳到的点 $x$ 是白色,那么染色为黑扔进队列,因为将花看做点的话是可以往外面匹配的,由于我们不确定是花中的哪个节点往外匹配,故均染色为黑。

      注意跳的时候还需要更新并查集的 $fa$ 。

带花树的时间复杂度是 $O(n^3)$ 的,但在实际实现中跑不到上界,因此一般 $n=1000$ 也能跑跑。

关于跳 $lca$ 和开花两个部分没看懂 (代码) 的建议画画图:

带花树

蓝点即为黑点,橙点即为白点,粗边即为匹配,有向的细边其实就是 $pre$ 指针。


一些题目

Luogu-P6113 一般图最大匹配
UOJ #79. 一般图最大匹配

模板题。

$\rm{Code_1:}$

namespace _ {
    queue <int> q;
    int tim,fa[N],vis[N],pre[N],col[N],match[N];
    inline int find(int x) {
        while(x!=fa[x]) x=fa[x]=fa[fa[x]];
        return x;
    }
    inline int lca(int x,int y) {
        ++tim,x=find(x),y=find(y);
        for(;;swap(x,y)) {
            if(!x) continue;
            if(vis[x]==tim) return x;
            vis[x]=tim,x=match[x]?find(pre[match[x]]):0;
        }
    }
    inline void blossom(int x,int y,int t) {
        while(find(x)!=t) {
            pre[x]=y,y=match[x];
            if(col[y]==2) col[y]=1,q.push(y);
            fa[x]=fa[y]=t,x=pre[y];
        }
    }
    inline bool solve(int s) {
        memset(pre,0,sizeof(pre));
        memset(col,0,sizeof(col));
        for(int i=1;i<=n;++i) fa[i]=i;
        while(!q.empty()) q.pop();
        q.push(s),col[s]=1;
        while(!q.empty()) {
            int u=q.front();q.pop();
            for(int v:G[u]) {
                if(!col[v]) {
                    col[v]=2,pre[v]=u;
                    if(!match[v]) {
                        for(int las;u;v=las,u=pre[v])
                            las=match[u],match[u]=v,match[v]=u; 
                        return true;
                    } else q.push(match[v]),col[match[v]]=1;                    
                } else if(col[v]==1&&find(u)!=find(v)) {
                    int t=lca(u,v);
                    blossom(u,v,t),blossom(v,u,t);
                }
            }
        }
        return false;
    }

} using namespace _;

int main() {
    IN(n),IN(m);
    for(int i=1;i<=m;++i) addedge();
    for(int i=1;i<=n;++i) if(!match[i]&&solve(i)) ++ans;
    printf("%d\n",ans);
    return puts(""),0;xuyaozhuyi
} 

UOJ #171.「WC2016」挑战 NPC

可以将一个筐子拆成三个点,对于一个球也要和这三个点连边,并且三个点之间连边。

如果一个筐子是合法的,那么筐子的三个点之间一定存在一个匹配。

由于每一个球一定匹配,答案为最大匹配数 $-n$ 。

注意点数是 $n+m+m+m$ 而非 $n$ ,清空数组或者定义 $fa$ 时需要注意。

$\rm{Code_2:}$

namespace Flower_tree {
    queue <int> q;
    int tim,fa[N],vis[N],pre[N],col[N],match[N];
    inline int find(int x) {
        while(x!=fa[x]) x=fa[x]=fa[fa[x]];
        return x;
    }
    inline int lca(int x,int y) {
        ++tim,x=find(x),y=find(y);
        for(;;swap(x,y)) {
            if(!x) continue;
            if(vis[x]==tim) return x;
            vis[x]=tim,x=match[x]?find(pre[match[x]]):0;
        }
    }
    inline void blossom(int x,int y,int t) {
        while(find(x)!=t) {
            pre[x]=y,y=match[x];
            if(col[y]==2) col[y]=1,q.push(y);
            fa[x]=fa[y]=t,x=pre[y];
        }
    }
    inline bool check(int s) {
        memset(pre,0,sizeof(pre));
        memset(col,0,sizeof(col));
        for(int i=1;i<=L;++i) fa[i]=i;
        while(!q.empty()) q.pop();
        q.push(s),col[s]=1;
        while(!q.empty()) {
            int u=q.front();q.pop();
            for(int v:G[u]) {
                if(!col[v]) {
                    col[v]=2,pre[v]=u;
                    if(!match[v]) {
                        for(int las;u;v=las,u=pre[v])
                            las=match[u],match[u]=v,match[v]=u; 
                        return true;
                    } else q.push(match[v]),col[match[v]]=1;                    
                } else if(col[v]==1&&find(u)!=find(v)) {
                    int t=lca(u,v);
                    blossom(u,v,t),blossom(v,u,t);
                }
            }
        }
        return false;
    }
    inline int solve() {
        int ans=0;
        for(int i=1;i<=L;++i) if(!match[i]&&check(i)) ++ans;
        return ans;
    }
} using namespace Flower_tree;

inline void Main() {
    memset(match,0,sizeof(match)),
    memset(vis,0,sizeof(vis)),tim=0;
    IN(n),IN(m),IN(e),L=n+m+m+m;
    for(int i=1;i<=L;++i) G[i].clear();
    int x,y;
    for(int i=1;i<=e;++i) {
        IN(x),IN(y);
        addedge(x,n+y),addedge(x,n+m+y),addedge(x,n+2*m+y);
    }
    for(int i=1;i<=m;++i)
        addedge(n+i,n+m+i),addedge(n+i,n+2*m+i),addedge(n+m+i,n+2*m+i);
    printf("%d\n",solve()-n);
    for(int i=1;i<=n;++i) printf("%d ",(match[i]-n-1)%m+1);
    return puts(""),void();
}

int T;
int main() {
    IN(T);
    while(T--) Main();
    return 0;
} 

分类: 文章

Qiuly

QAQ

1 条评论

ticmis · 2020年5月14日 10:20 上午

orz%%

发表评论

电子邮件地址不会被公开。 必填项已用*标注