匈牙利算法(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