序言

• km算法的学习过程可谓艰辛，各种奇怪的hack层出不穷，而网络资料给出的debug也不是很全面。特此写下本篇题解供各oier参考。
• 后记的相关内容总结了km算法在应用时的一些小技巧，和一些有趣的hack及其应对方式。（因为本蒟蒻的确被卡了很多次，求大神轻喷。）
• 鸣谢：ltao。没有他，我不可能见到这些神奇的hack与debug，也无法得到有效且及时的质疑与纠正。

算法介绍

• 算法简介：km算法（Kuhn－Munkres算法），是一种在二分图上求解最大权完美匹配的算法，用邻接矩阵存图即可。相比费用流较高的复杂度，km算法有着更为优秀的效率，但局限性在于只能做匹配，而不像费用流那样灵活可变。

• 前置知识：匈牙利算法的bfs写法（附上匈牙利和km算法的bfs模板，可供参考，欢迎交流）

• km算法的核心思路在于：

  • 定义顶标lx[i],ly[i]，则对于每一条边，都有性质lx[u]+ly[v]>=e[u][v]。
  • 当且仅当lx[u]+ly[v]=e[u][v]时，我们称该边为相等边。
  • 所有点和所有相等边所组成的子图称为相等子图。
  • 核心算法：贪心地将増广所需的边中，边权最大的那些边变成相等边，即逐渐扩大相等子图。
  • 核心性质：扩大相等子图至其刚好有完美匹配时，该匹配即为原图的最大权完美匹配（很好理解，因为扩大相等子图的过程是贪心的）

  由此，我们便能将km算法简单地理解为：匈牙利算法+扩大相等子图

• 顶标的设计是km的精髓，这里参考ltao的定义：

  $ly[i]$右部点的顶标 $vx[i]$左部点遍历标记 $vy[i]$右部点遍历标记 $px[i]$左部点匹配 $px[i]$右部点匹配 $slack[i]$对于指向右部点$i$的所有边，$min(lx[u]+ly[i]-e[u][i])$的值，即松弛量（初始化为inf） PS:当slack[i]=0，表示对于右部点i，相等子图中有一条指向它的边

  而修改顶标的思路可以具体看代码，核心语句如下（copy的是下面bfs正解的过程）：

  if(vx[i])lx[i]-=d;//对于vx[i]=0的情况我们根本没有讨论，实际上也并不需要讨论
  if(vy[i])ly[i]+=d;else slack[i]-=d;

  这样修改的目的是保证已在相等子图中的边两侧顶标和不变，同时通过左部点顶标的减小实现向相等子图中拉进新相等边的目的。

  如果还不是很理解可以画个图，对于原图中某条边：

  这里提供ltao's blog以加深理解。他充分讨论了修改顶标对所有边产生的影响，还提出了关于序号3的一些非常重要的观点，本篇题解在后记中也会提到。

模板分析（p6577）

首先提示坑点：

1. 边权最小约-1e7，所以如果要添加虚边将图补成完全图，记得初始边权设为-inf。（不补全而直接忽视不存在边在本题也可行，依照个人习惯即可）
2. 权值和需要用long long​存储。

直接打出匈牙利dfs写法+扩大相等子图的模板，初学者一定要先练熟这个。

const int MAXN=510;

int n,m;
int e[MAXN][MAXN];

int lx[MAXN],ly[MAXN],py[MAXN],d;
bool vx[MAXN],vy[MAXN];

bool dfs(int u)
{
    vx[u]=1;
    for(int i=1;i<=n;++i)if(!vy[i])
    {
        if(lx[u]+ly[i]==e[u][i])
        {
            vy[i]=1;
            if(!py[i] || dfs(py[i]))
            {
                py[i]=u;
                vy[i]=1;
                return 1;
            }
        }
        else d=min(d,lx[u]+ly[i]-e[u][i]);
    }
    return 0;
}

int main()
{
    for(int i=1;i<=n;++i)
    {
        while(1)
        {
            memset(vx,0,sizeof(vx));
            memset(vy,0,sizeof(vy));
            d=inf;
            if(dfs(i))break;
            for(int j=1;j<=n;++j)
            {
                if(vx[j])lx[j]-=d;
                if(vy[j])ly[j]+=d;
            }
        }
    }
}

结果成功tle，不得不说卡km+dfs的题目真的不多。

我们简单分析一下复杂度：

• 每次扩大相等子图最少只能加入一条相等边，也就是最多会进行n^2次扩大相等子图。
• 每次扩大相等子图后都需要进行dfs増广，单次复杂度可达n^2。

也就是说，km+dfs的复杂度完全可以卡到n^4。

考虑如何优化，我们不难发现每次扩大相等子图之后，都要从増广起点重新开始dfs，这个过程是有明显的时间浪费的。

能不能在扩大相等子图之后，保留上次状态呢？

答案是可行的，我们只需要换用bfs写法：在每次扩大子图后，都记录一下新加入的相等边所为我们提供的新増广方向，然后从此处继续寻找増广路即可。

扩大相等子图复杂度：

• 每次扩大相等子图最少只能加入一条相等边，也就是最多会进行n^2次扩大相等子图。
• 每次扩大相等子图复杂度n，无需额外増广，从上次起点继续増广即可。

増广复杂度：

• 每个左部点需要1次増广，共有n个左部点。
• 单次増广复杂度可达n^2。

由此可见，通过简单的状态延续策略，我们成功将km算法的复杂度降到了n^3。

const int MAXN=510;

int n,m;
int e[MAXN][MAXN];

int lx[MAXN],ly[MAXN],slack[MAXN];
int px[MAXN],py[MAXN],pre[MAXN];
bool vx[MAXN],vy[MAXN];

queue<int> q;
void aug(int v)
{
    int t;
    while(v)
    {
        t=px[pre[v]];
        px[pre[v]]=v;
        py[v]=pre[v];
        v=t;
    }
}
void bfs(int s)
{
    memset(vx,0,sizeof(vx));
    memset(vy,0,sizeof(vy));
    fill(slack+1,slack+n+1,inf);

    while(!q.empty())q.pop();
    q.push(s);

    while(1)
    {
        while(!q.empty())
        {
            int u=q.front();q.pop();
            vx[u]=1;
            for(int i=1;i<=n;++i)if(!vy[i])
            {
                if(lx[u]+ly[i]-e[u][i]<slack[i])
                {
                    slack[i]=lx[u]+ly[i]-e[u][i];
                    pre[i]=u;
                    if(slack[i]==0)
                    {
                        vy[i]=1;
                        if(!py[i]){aug(i);return;}
                        else q.push(py[i]);
                    }
                }
            }
        }
        int d=inf;
        for(int i=1;i<=n;++i)if(!vy[i])d=min(d,slack[i]);
        for(int i=1;i<=n;++i)
        {
            if(vx[i])lx[i]-=d;
            if(vy[i])ly[i]+=d;else slack[i]-=d;
        }
        for(int i=1;i<=n;++i)if(!vy[i])
        {
            if(slack[i]==0)
            {
                vy[i]=1;
                if(!py[i]){aug(i);return;}
                else q.push(py[i]);
            }
        }
    }
}

int main()
{
    for(int i=1;i<=n;++i)bfs(i);
}

还有一种迭代bfs的写法，是榜一Wendigo大神所采用的，可能不像队列写法这么易懂，但码量明显大幅下降。

另外Wendigo还提到迭代写法可以卡到n^4，但在下不是很理解该怎样构造数据，也不清楚队列写法是否同样可以hack，希望评论区有大神可以解答。

这两篇博客分别使用的是队列写法和迭代写法，供参考。

后记

> //这个其实是有一点小问题的，但是没啥大问题 ~~说的这么玄学谁能明白啊~~ ## 1.虚点虚边的添加 因为出题人保证了数据存在完备匹配，所以就算不是完全二分图也可以大胆去跑km。 但有些题目需要特判无解情况，即不存在完美匹配； 还有些题目告诉你，就算非完美匹配也无所谓，为了让权值和最大可以允许某些点无匹配而孤独终生。 这类题目就要求选手对km算法拥有比较清晰的理解，那么请你思考一下，分别应该如何应对？ ok揭晓答案。 首先无论哪种情况，我们都要保证左部点个数小于等于右部点个数，通过为右部点添加**虚点**来实现。 然后，我们要将原本不存在的边连成**虚边**。 对于需要特判无解的题目，我们需要极力避免选择虚边，也就是将虚边边权设为$-inf$，如果被迫选了$-inf$的边就输出无解。 对于允许非完美匹配的题目，我们允许选取虚边，也就是将虚边边权设为0即可。 这样，我们就可以在完全二分图上跑km求解。（当然对于无解，你也可以选择只加一个虚点作为退路，跑一般二分图的km，如果该虚点被匹配则必然无解） 不过这只是一种个人比较喜欢的通用策略，对于特判无解的那种题目，还有一种常见策略： 即当$d$很大时，说明某个$slack[i]$很大，无法扩大子图，也就是无解。但为什么这个很大不是$inf$呢？原因在于我们bfs写法为了加速就必须修改顶标同时修改$slack[]$，可能会改变$slack[]=inf$的值，非常不方便判无解。 还有人会说用dfs时如果无解，能保证$d=inf$。但这种写法慢是一方面，另一方面就是我将要提到的死循环hack。 ## 2.可能的死循环hack dfs写法直接判$d=inf$无解，是有死循环风险的。 这个简单的小hack能坑到很多初学者（包括我），下面详细说一下。 借用ltao的话来说：一共有最多$n^2$条边，却只有$2n$的顶标，这就好像要用$2n$个元来满足$n^2$个方程成立，很明显是存在方程组无解的可能性的！ 而体现在原图中便是**不是所有边都能成为相等边**，而**相等子图可能如何设置顶标也无法等于原图**！ 而体现在算法中，就是总有一些边，我们无论如何也拉不进来，或者拉进一些边的同时拉出一些边。（将相等边拉出相等子图的原理，就是上文提到的$vx[u]=0,vy[v]=1$所导致的结果） 这就会导致这样一种可能的后果：由于dfs的鼠目寸光，我们会先从u遍历到某条非相等边<u,v>，并记录下$d=lx[u]+ly[v]-e[u][v]$；然后在后续的遍历过程中，我们通过其他路径遍历到了v点。 此时，$vx[u]=vy[v]=1$，可$0<d<inf$，我们一方面拉不进这条边，另一方面判不出来无解，只能陷入死循环。（[hdu2426的discuss](http://acm.hdu.edu.cn/discuss/problem/post/reply.php?postid=39470&messageid=1&deep=0)中就有大神造出了这样hack） 那为什么bfs写法就能防止死循环？ 因为bfs写法不是在遍历过程中直接记录$d$，而是走遍所有能遍历的点后，用$slack[]$来计算$d$。而且bfs写法判无解通常用虚点虚边，也就能避免死循环情况出现。 --- upd:对hdu2426的hack原理没看太明白的，可以去看看[ltao](https://www.luogu.com.cn/blog/lov-kyn/solution-p6577)的题解，有我依此做的一个配图样例。（~~我就不在这里贴出来了~~）