匈牙利算法，二分图最大基数匹配（过山车，hdu 2063）

匈牙利算法，二分图最大基数匹配（过山车，hdu 2063）

参考博客：.html

女生对男生有要求，但男生对女生无要求，即有求必应。因此有向边就变成了无向边。

在建立邻接矩阵MAP[u][v]时只建立有向边意思是女生u与男生v可以匹配，而女生v不一定和男生u匹配。

hungary()函数的意思是遍历所有女生，对每个女生尝试匹配，或许可以一次匹配成功，或许要修改一下之前的匹配方式才能成功，但不允许破坏之前的匹配，即不能让已匹配的女生失配。

link数组用于记录先前的匹配情况，以便寻增广路并修改。只memset一次。

vis数组用于记录当前女生的搜索状态，如果vis[v]了，说明之前已经对男生v寻找过增广路而且失败了，所以不再对他dfs，因为如果寻找增广路成功就直接返回true了，只有失败了才会继续搜索，然后遇到先前失败的情况。

dfs()函数就是用来寻增广路的，对于某个女孩，如果她找到了某个未匹配的男孩，那么就直接匹配，否则就尝试让与这个男孩匹配的女孩重新找一个男孩，一旦成功，就一路修改link数组然后返回true。搜寻完所有结果都不行就返回false。

模板

/****************************************************
二分图匹配（匈牙利算法的DFS实现）
INIT：g[][]两边定点划分的情况
CALL:res=hungary();输出最大匹配数
优点：适于稠密图，DFS找增广路快，实现简洁易于理解
时间复杂度:O(VE);
****************************************************/
const int MAXN=1000;
int uN,vN;  //u,v数目
int g[MAXN][MAXN];//编号是0~n-1的 
int linker[MAXN];
bool used[MAXN];
bool dfs(int u)
{int v;for(v=0;v<vN;v++)if(g[u][v]&&!used[v]){used[v]=true;if(linker[v]==-1||dfs(linker[v])){linker[v]=u;return true;}    }  return false;  
}    
int hungary()
{int res=0;int u;memset(linker,-1,sizeof(linker));for(u=0;u<uN;u++){memset(used,0,sizeof(used));if(dfs(u))  res++;} return res;   
}     

代码

#include<bits/stdc++.h>
#define maxn 510
using namespace std;int K,M,N;
///
//hungary
bool MAP[maxn][maxn];
int link[maxn];
bool vis[maxn];bool dfs(int u)
{for(int v=1;v<=N;v++)if(MAP[u][v]&&!vis[v]){vis[v]=true;if(!link[v]||dfs(link[v])){link[v]=u;return true;}}return false;
}int hungary()
{int ret=0;memset(link,0,sizeof(link));for(int i=1;i<=M;i++){memset(vis,0,sizeof(vis));if(dfs(i))ret++;}return ret;
}
///int main()
{while(scanf("%d",&K)==1&&K){memset(MAP,0,sizeof(MAP));scanf("%d %d",&M,&N);int u,v;for(int i=1;i<=K;i++){scanf("%d %d",&u,&v);MAP[u][v]=1;}printf("%dn",hungary());}return 0;
}