KM=费用流
dengyaotriangle · · 个人记录
好像是个众所周知的东西，感觉挺有意思的。
对于最大权匹配问题，WC2020 中介绍过一种可以完全覆盖费用流算法的修改版 KM，但实际上可以发现，KM 与费用流几乎是等价的。
原始 KM 算法的适用范围是在非负权完全二分图上的最大完美匹配。这里它可以被理解成一个求对偶问题——最小顶标和的算法。
但对于任意二分图的指定大小最大匹配。此时其似乎并不可以简单的施加一个对偶而被解释成类似的问题。
但如果我们将 KM 过程中的
为啥等价呢，其实只需要注意到，若开始时节点的
而 KM 的一轮增广中，不断调整顶标，其实是一个 dijkstra 状物。每次选择最近的未确定的，将其最短路确定。只不过这里不是显式的维护最短路，而是直接调整节点的高度，使得所有确定了最短路的点与起点的调整后的距离为
那么为什么 dijkstra 费用流过不去 KM 可以过的题呢，小编也感到很惊讶，但专家研究发现原来是 dijkstra 费用流常数太大了。其实从某种角度上来说， KM 只不过是一个加了许多常数优化的费用流罢了，因为 KM 所干的事情和费用流都是一样的，都是每次寻找一个最短路进行增广，而 KM 利用了更多二分图性质，所以常数小。
以下就是 KM 的完全费用流等价版本——外层 while 循环跑到第
// nl,nr: #point of left || right
// wx[i][j]: does edge (ai,bj) exist?
// w[i][j]: weight of edge (ai,bj)
for(int i=1;i<=nr;i++)y[i]=0;
for(int i=1;i<=nl;i++)x[i]=inf;
while(1){
for(int i=1;i<=nl;i++)visx[i]=!matx[i];
for(int i=1;i<=nr;i++)slk[i]=inf*3,visy[i]=0,fa[i]=0;
for(int i=1;i<=nl;i++)if(visx[i]){
for(int j=1;j<=nr;j++)if(wx[i][j]){
long long cur=x[i]+y[j]-w[i][j];
if(cur<slk[j])slk[j]=cur,fa[j]=i;
}
}
bool ok=0;
while(1){
long long dlt=inf*3;
for(int i=1;i<=nr;i++)if(!visy[i])dlt=min(dlt,slk[i]);
if(dlt>=inf*2)break;
for(int i=1;i<=nl;i++)if(visx[i])x[i]-=dlt;
for(int i=1;i<=nr;i++)if(visy[i])y[i]+=dlt;else if(fa[i])slk[i]-=dlt;
for(int i=1;i<=nr;i++)if(!visy[i]&&!slk[i]){
visy[i]=1;
if(!maty[i]){
ok=1;
for(int u=i;u;swap(matx[fa[u]],u))maty[u]=fa[u];
break;
}else{
int p=maty[i];
visx[p]=1;
for(int i=1;i<=nr;i++)if(!visy[i]&&wx[p][i]){
long long cur=x[p]+y[i]-w[p][i];
if(cur<slk[i])slk[i]=cur,fa[i]=p;
}
}
}
if(ok)break;
}
if(!ok)break;
long long ans=0;
for(int i=1;i<=nl;i++)if(matx[i])ans+=w[i][matx[i]];
cout<<ans<<'\n';
}而普通 KM 的时候我们并不必须要将