二分图带权最大匹配——KM算法
Kevin_Mamba · · 个人记录
用不惯博客园，还是洛谷比较亲切。
参考文献
说实话，这就比那个匈牙利要难多了。
例题1
搞不懂这个为什么是绿题，而一大堆匈牙利模板都是蓝题。
KM 算法
-
先分为左点集和右点集。
-
初始化左点集每个点的期望（和右点集所有连边中边权的最大值）。
-
枚举左点集，不停
dfs ，直到匹配到。 -
匹配：先枚举和自己有连边的所有右点。
-
若连边边权为期望值，看下与所连右点能否匹配，否则记录该边权与期望值的差。
-
判断期望边是否能匹配时，进行
dfs ，和匈牙利算法有异曲同工之妙。 -
若能匹配枚举下一个左点，否则改变期望值。
-
改变时，取所有右点与期望的差距的最小值，所有涉及左点减去这个值，右点加上这个值，未涉及右点的期望差距减去这个值。详见代码。
#include<bits/stdc++.h>
#define il inline
#define re register
using namespace std;
const int N=24;
int n,a[N][N],p[N],ans;
int ex[N],ex_2[N],dif[N];
// 期望值，相对期望的差值
bool vis[N],vis_2[N];
// 是否参与搜索
il bool dfs(re int u)
{
vis[u]=true;
for(re int v=1;v<=n;v++)
{
if(vis_2[v]) continue;
re int diff=ex[u]+ex_2[v]-a[u][v];
if(diff==0)
{
vis_2[v]=true;
if(p[v]==0||dfs(p[v]))
{
p[v]=u;
return true;
}
}
else
dif[v]=min(dif[v],diff);
// 还差多少达到期望
}
return false;
// 记得说不行
}
il void KM()
{
for(re int i=1;i<=n;i++)
for(re int j=1;j<=n;j++)
ex[i]=max(ex[i],a[i][j]);
for(re int i=1;i<=n;i++)
{
memset(dif,0x7e7e7e7e,sizeof dif);
// cerr<<dif[16]<<endl;
while(true)
{
memset(vis,0,sizeof vis);
memset(vis_2,0,sizeof(vis_2));
if(dfs(i)) break;
re int dif_min=INT_MAX;
// 最小期望差值
for(re int j=1;j<=n;j++)
if(!vis_2[j]) dif_min=min(dif_min,dif[j]);
for(re int j=1;j<=n;j++)
{
if(vis[j]) ex[j]-=dif_min;
if(vis_2[j]) ex_2[j]+=dif_min;
else dif[j]-=dif_min;
}
// 修改期望
}
}
}
int main()
{
scanf("%d",&n);
for(re int i=1;i<=n;i++)
for(re int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(re int i=1;i<=n;i++)
for(re int j=1;j<=n;j++)
{
re int b; scanf("%d",&b);
a[j][i]*=b;
// 审题
}
KM();
for(re int i=1;i<=n;i++)
ans+=a[p[i]][i];
printf("%d\n",ans);
return 0;
}本蒟蒻语文不好，表述可能不清，建议食用参考文献。
实战演练 暨 手撕蓝题
例题2
简要题意：求带权二分图匹配最大值和最小值。
就当是复习吧，最小值只需将权值
#include<bits/stdc++.h>
#define il inline
#define re register
using namespace std;
const int N=245;
int n,a[N][N];
int ex[N],ex_2[N],dif[N],p[N];
bool vis[N],vis_2[N];
il bool dfs(re int u)
{
vis[u]=true;
for(re int v=1;v<=n;v++)
{
if(vis_2[v]) continue;
re int diff=ex[u]+ex_2[v]-a[u][v];
if(diff==0)
{
vis_2[v]=true;
if(p[v]==0||dfs(p[v]))
{
p[v]=u;
return true;
}
}
else
dif[v]=min(dif[v],diff);
}
return false;
}
il int KM()
{
memset(ex_2,0,sizeof ex_2);
memset(p,0,sizeof p);
for(re int i=1;i<=n;i++)
for(re int j=1;j<=n;j++)
ex[i]=max(ex[i],a[i][j]);
for(re int i=1;i<=n;i++)
{
memset(dif,0x7e7e7e7e,sizeof dif);
while(true)
{
memset(vis,0,sizeof vis);
memset(vis_2,0,sizeof vis_2);
if(dfs(i)) break;
re int dif_min=INT_MAX;
for(re int v=1;v<=n;v++)
if(!vis_2[v]) dif_min=min(dif_min,dif[v]);
for(re int j=1;j<=n;j++)
{
if(vis[j]) ex[j]-=dif_min;
if(vis_2[j]) ex_2[j]+=dif_min;
else dif[j]-=dif_min;
}
}
}
re int ret=0;
for(re int v=1;v<=n;v++)
ret+=a[p[v]][v];
return ret;
}
int main()
{
scanf("%d",&n);
for(re int i=1;i<=n;i++)
for(re int j=1;j<=n;j++)
scanf("%d",&a[i][j]),a[i][j]*=-1;
printf("%d\n",-KM());
for(re int i=1;i<=n;i++)
for(re int j=1;j<=n;j++)
a[i][j]*=-1;
printf("%d\n",KM());
return 0;
}