匈牙利算法(hungary)
匈牙利算法是用来计算最大匹配,用了增广路思想
增广路:
dfs实现
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 10;
int visx[maxn],visy[maxn];
int match[maxn],map[maxn][maxn];
int nx,ny;
void res;
int find(int u)
{
visx[u] = 1;
for(int v = 0; v < ny; v++){
if(!visy[v] && map[u][v]){
visy[v] = 1;
if(match[v] == -1 || path(match[v])){
match[v] = u;
return true;
}
}
}
return false;
}
void hungary()
{
res = 0;
memset(match,-1,sizeof(match));
for(int i = 0 ; i < nx; i++){
memset(visx,0,sizeof(visx));
mesmet(visy,0,sizeof(visy));
if( find(i))
res++:
}
printf("%d\n",res);
}
原文:http://www.cnblogs.com/zero-begin/p/4545063.html