【图论】【一般图匹配】带花树算法详解

· · 题解

算法介绍

模板分析

直接以uoj79为模板讲解。luogu数据过水，无法卡掉所有错误做法。

  1. 创造性的算法往往是在已有基础上改进形成的，带花树算法亦是如此。

    我们考虑在一个一般图中，不存在奇数环，即为一颗存在偶数环的树，可以想到直接对其进行二分图染色+匈牙利算法（二者可以同时进行）解决，这是带花树算法的基础框架。（code省略了部分细节）

bool bfs(int s)
{
    while(!q.empty())
    {
        u=q.front();q.pop();
        for(int v=1;v<=n;++v)if(e[u][v])//枚举可达节点 
        {
            if(!col[v])//未遍历过，即遍历路径仍为树结构 
            {
                pre[v]=u;//记录前驱 
                if(!match[v]){aug(v);return 1;}//找到増广路终点，进行増广
                else{col[v]=2;col[match[v]]=1;q.push(match[v]);}//v点已有匹配，令u=match[v] 
            }
            else//环，处理见下 
        }
    }
    return 0;//増广失败 
}

  1. 思考对奇数环的讨论。我们称奇数环为花，如下图所示：

    图中加粗边为已有匹配。定义每对已有匹配的出点为u（col=1，颜色为绿），入点为v（col=2，颜色为白）。（这仅是一种不严格的颜色命名）

    如果染色増广过程中发现了奇数环，则花的根节点必然为u型点。（想一想如果花根是v型节点，是否还会出现染色冲突？）

    以A点为起点进行染色増广。可见在染色过程中，I与J产生冲突。带花树算法的处理方法是：将花缩成一点，该点作为u型点向花外遍历，在修改増广路的时候再将花展开。（这只是一种理解方式，实现时并不真正进行缩展，而是用并查集模拟缩花的过程，用反向pre保证花内部増广路的正确）

    首先，我们考虑用一个并查集维护花根之间的关系（因为可能出现花套花的情况），即将花内所有分花根合并到新出现的总花根上。

    然后处理花内部的増广路关系，这是带花树算法的精髓：

    1. 在产生冲突前，奇数环上所有出点（即绿色点）都已进行了从环内向环外的遍历。

    2. 产生冲突后，我们分别以I和J为新増广路的u，向对方方向继续染色増广。可以发现，对方方向上原本的入点（即白色点），可以作为出点向花外遍历（如图中H->N），而这条増广路是从花内距花根较远的一条路延伸来的（如图中J->I->H->N)。

    3. 考虑如何记录这条较远的非常规路径。我们知道，在匈牙利算法中，对于每一对匹配中的入点v，我们都会有一个pre指向其前驱匹配的出点u（即图中的红色边），也就是说仅有v型点具有pre。

      然而在花中，所有点可以作为u型点向外遍历，也就没有了严格的u、v区分。因此无论u、v染色情况如何，我们为花中所有匹配对之间建立相互的pre，具体实现见下（注意由于原本已有部分pre，即红色边，我们要根据特殊性质去建立剩余的pre，即蓝色边）。

      特别注意，如果到了u为根节点，就不要再反向建立pre了，因为它所在匹配对并不完全属于花！

    这样，无论以哪个点作为u向环外遍历，我们在花内部都能得到正确的増广路。（想一想，以图中表示出的白色点和绿色点分别为起点，向花外遍历，其在花内体现出的増广路分别是什么样的？）

else//环 
{
    if(get_fa(u)==get_fa(v))continue;//该环已被缩成一点，不必处理 
    if(col[v]==1)//奇数环，需要将花缩成花根一点 
    {
        //此时的u、v均为出点，不适用命名原则 
        int r=lca(u,v);//寻找lca，即总花根 
        shrink(u,v,r);//分别从两个方向，建立反向pre，保证花内部増广路正确性 
        shrink(v,u,r);
    }
    //偶数环不必处理 
}

  1. 你可能会注意到上面的程序框架中出现了lca和shrink这两个函数。

    关于lca，我们只要朴素寻找总花根即可，因为遍历的起点总是在变的，无法用倍增lca来加速。

    关于shrink，思想就是上述对于花内増广路的维护，也就是建立反向pre。

    连带修改増广路的aug函数一起，code如下：

void aug(int v)//从v点开始修改増广路 
{
    int t;
    while(v)
    {
        t=match[pre[v]];//临时记录下一次的v
        match[v]=pre[v];
        match[pre[v]]=v;
        v=t; 
    }
}
int cnt,vis[MAXN];
int lca(int u,int v)//寻找两个节点的总花根 
{
    ++cnt;//每次lca选用不同的cnt作为判断条件 
    u=get_fa(u);//保证操作对象时刻为分花根 
    v=get_fa(v);
    while(vis[u]!=cnt)//某一点同时两次被染色，即为总花根 
    {
        vis[u]=cnt;
        u=get_fa(pre[match[u]]);//保证操作对象时刻为分花根 
        if(v)swap(u,v);//切换操作对象 
    }
    return u;
}
void shrink(int u,int v,int r)//以r为总花根，将花缩成花根一点，并建立内部的反向pre
{
    while(get_fa(u)!=r)//当已达到总花根，说明缩花任务完成 
    {
        //每次循环起初的v为上个匹配的v 
        pre[u]=v;//建立反向pre，保证増广路
        v=match[u];
        if(col[v]==2){col[v]=1;q.push(v);}//花内所有v，都应以u身份向外増广 
        if(get_fa(u)==u)fa[u]=r;//如果某一点为分花根，将其合并到总花根上 
        if(get_fa(v)==v)fa[v]=r;
        u=pre[v];//切换操作对象 
    }
}

于是基础的匈牙利算法和对奇数环的讨论全部完成，带花树算法成功得到实现。

时间复杂度