KM算法整理

算法整理"/>

KM算法整理

#include<bits/stdc++.h>
using namespace std;
const int maxn=505;int a[maxn][maxn];///二分图左右点间边权
int ly[maxn];///右点顶标
int lx[maxn];///左点顶标
int match[maxn];///左点匹配的右点编号
bool visx[maxn];///左点标记
bool visy[maxn];///右点标记int dfs(int x)
{visx[x]=1;for(int i=1,i<=n;i++)///遍历右点{if(!visy[i]&&lx[x]+ly[i]==a[x][i])///右点没有被访问过且顶标和等于边权（用于判断该边是否为有效边）{visy[i]=1;if(!match[i]||dfs(match[i])){match[i]=x;return 1;}}}return 0;
}int main()
{memset(lx,0xf7,sizeof(lx));///赋值为负无穷memset(ly,0,sizeof(ly));///右点顶标初始化为0memset(match,0,sizeof(match));///视情况赋值为0 or -1for(int i=1;i<=n;i++)///将左点顶标初始化为最大边权for(int j=1;j<=m;j++)lx[i]=max(a[i][j],lx[i]);for(int i=1;i<=n;i++)///枚举左点，给左点匹配右点{while(1)///不找着不停{memset(visx,0,sizeof(visx));memset(visy,0,sizeof(visy));if(dfs(i)) break;///如果有有效边就给下一个左点匹配，如果没有接下来修改顶标int d=0x7f7f7f7f;///d是更换匹配后最少的损失数for(int j=1;j<=n;j++)///遍历维护最少损失{if(visx[j]){for(int k=1;k<=m;k++){if(!visy[k]) d=min(d,lx[j]+ly[k]-a[j][k]);}}}if(d==0x7f7f7f7f) return -1;///无法匹配for(int j=1;j<=n;j++) if(visx[j]) lx[j]-=d;///顶标修改for(int j=1;j<=m;j++) if(visy[j]) ly[j]+=d;}}return 0;
}