以上是匈牙利算法的关键代码
- const int INF = 0x3f3f3f3f;
- const int MAXN=510;
- int uN,vN;//u,v数目
- int g[MAXN][MAXN];//构图
- int link[MAXN]; //link[v]=u表示右边对左边的匹配
- bool used[MAXN];//是否访问过
- bool dfs(int u)//从左边开始找增广路径
- {
- int v;
- for(v=0;v<vN;v++)//右边顶点编号从0开始
- {
- if(g[u][v]&&!used[v]) //如果存在通路,且从u开始搜索时该点没访问过
- {
- used[v]=true;
- if(link[v]==-1 || dfs(link[v])) //找增广路
- {
- link[v]=u;
- return true;
- }
- }
- }
- return false;
- }
- int hungary()
- {
- int res=0;
- int i,u;
- memset(link,-1,sizeof(link));
- for(u=0;u<uN;u++)
- {
- memset(used,0,sizeof(used));
- if(dfs(u))
- res++;
- }
- return res;
- }
来源: http://www.phpxs.com/code/1004114/