题解 P6577 【【模板】二分图最大权完美匹配】
Singercoder · · 题解
序言
- 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）
首先提示坑点：
- 边权最小约-1e7，所以如果要添加虚边将图补成完全图，记得初始边权设为
-inf 。（不补全而直接忽视不存在边在本题也可行，依照个人习惯即可） - 权值和需要用
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的复杂度完全可以卡到
考虑如何优化，我们不难发现每次扩大相等子图之后，都要从増广起点重新开始dfs，这个过程是有明显的时间浪费的。
能不能在扩大相等子图之后，保留上次状态呢？
答案是可行的，我们只需要换用bfs写法：在每次扩大子图后，都记录一下新加入的相等边所为我们提供的新増广方向，然后从此处继续寻找増广路即可。
扩大相等子图复杂度：
- 每次扩大相等子图最少只能加入一条相等边，也就是最多会进行
n^2 次扩大相等子图。 - 每次扩大相等子图复杂度
n ，无需额外増广，从上次起点继续増广即可。
増广复杂度：
- 每个左部点需要1次増广，共有
n 个左部点。 - 单次増广复杂度可达
n^2 。
由此可见，通过简单的状态延续策略，我们成功将km算法的复杂度降到了
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的写法，是榜一
另外
这两篇博客分别使用的是队列写法和迭代写法，供参考。