二分图匹配复习——匈牙利和KM算法

一，二分图最大匹配(匈牙利算法）

基本思想:没有机会，就创造机会

代码实现:

#include<bits/stdc++.h>
using namespace std;
const int N=500;
int mp[N][N];
int match[N],vis[N];
int k,m,n;  //k是连接数 m是左边个数 n是右边个数 
bool dfs(int x)
{
    for(int i=1; i<=n; i++)
    {
        if(mp[x][i]&&!vis[i]) //可以连接并且未连接过 
        {
            vis[i]=1;
            if(match[i]==0||dfs(match[i]))
            {
                match[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int x,y;
    while(scanf("%d",&k)&&k)
    {
        scanf("%d%d",&m,&n);
        memset(mp,0,sizeof(mp));
        memset(match,0,sizeof(vis));
        for(int i=0; i<k; i++)
        {
            scanf("%d%d",&x,&y);
            mp[x][y]=1;
        }
        int sum=0;
        for(int i=1; i<=m; i++)
        {
            memset(vis,0,sizeof(vis));
            if(dfs(i)) sum++;
        }
        printf("%d\n",sum);
    }
    return 0;
}

二，二分图最优匹配(KM算法）

基本思想:

（1） 初始化可行标杆 
（2） 用匈牙利算法寻找完备匹配 
（3） 若未找到完备匹配则修改可行标杆 

（4） 重复（2）（3）直到找到相等子图的完备匹配 

#include<iostream>#include<cstring>#include<cstdio>using namespace std;const int qwq=0x7fffffff;int w[1000][1000];  //w数组记录边权值 int line[1000],usex[1000],usey[1000],cx[1000],cy[1000];  //line数组记录右边端点所连的左端点， usex，usey数组记录是否曾访问过，也是判断是否在增广路上，cx，cy数组就是记录点的顶标 int n,ans,m;  //n左m右 bool find(int x){    usex[x]=1;    for (int i=1;i<=m;i++){        if ((usey[i]==0)&&(cx[x]+cy[i]==w[x][i])){   //如果这个点未访问过并且它是子图里面的边             usey[i]=1;            if ((line[i]==0)||find(line[i])){   //如果这个点未匹配或者匹配点能更改                 line[i]=x;                return true;            }        }    }    return false;}int km(){    for (int i=1;i<=n;i++){  //分别对左边点依次匹配         while (true){        int d=qwq;        memset(usex,0,sizeof(usex));        memset(usey,0,sizeof(usey));        if (find(i)) break;  //直到成功匹配才换下一个点匹配         for (int j=1;j<=n;j++)            if (usex[j])             for (int k=1;k<=m;k++)             if (!usey[k]) d=min(d,cx[j]+cy[k]-w[j][k]);  //计算d值         if (d==qwq) return -1;          for (int j=1;j<=n;j++)         if (usex[j]) cx[j]-=d;           for (int j=1;j<=m;j++)         if (usey[j]) cy[j]+=d;     //添加新边        }    }    ans=0;    for (int i=1;i<=m;i++)     ans+=w[line[i]][i];    return ans;}int main(){    while (~scanf("%d%d",&n,&m)){    memset(cy,0,sizeof(cy));    memset(w,0,sizeof(w));    memset(cx,0,sizeof(cx));    for (int i=1;i<=n;i++){     int d=0;     for (int j=1;j<=n;j++){      scanf("%d",&w[i][j]);      d=max(d,w[i][j]);   //此处顺便初始化左边点的顶标        }    cx[i]=d;    }    memset(line,0,sizeof(line));    printf("%d\n",km());}    return 0;}