1 /*==================================================*\ 2 | 二分图匹配(匈牙利算法DFS 实现) 3 | INIT: g[][]邻接矩阵; 4 | CALL: res = MaxMatch (); 5 | 优点:实现简洁容易理解,适用于稠密图,DFS 找增广路快。 6 | 找一条增广路的复杂度为O(E ),最多找V 条增广路,故时间复杂度为O(VE) 7 \*==================================================*/ 8 const int MAXN = 1000; 9 int uN, vN; // u, v 数目,要初始化!!! 10 bool g[MAXN][MAXN]; // g[i][j] 表示xi与yj相连 11 int xM[MAXN], yM[MAXN]; // 输出量 12 bool chk[MAXN]; // 辅助量检查某轮y[v]是否被check 13 bool SearchPath(int u) { 14 int v; 15 for (v = 0; v < vN; v++) 16 if (g[u][v] && !chk[v]) {//如果u到v是相连的,且v还没有用 17 chk[v] = true; 18 if (yM[v] == -1//第一次,用到了短路计算,否则SearchPath(-1)会出问题 19 || SearchPath(yM[v])) { 20 yM[v] = u; 21 xM[u] = v; 22 return true; 23 } 24 } 25 return false; 26 } 27 int MaxMatch() { 28 int u, ret = 0; 29 memset(xM, -1, sizeof(xM)); 30 memset(yM, -1, sizeof(yM)); 31 for (u = 0; u < uN; u++) 32 if (xM[u] == -1) {//u还没有匹配过 33 memset(chk, false, sizeof(chk));//保证每次都置成false 34 if (SearchPath(u)) 35 ret++; 36 } 37 return ret; 38 }
引用Matrix67的一段关于匈牙利算法的经典通俗解释:
研究了几个小时,终于明白了。说穿了,就是你从二分图中找出一条路径来,让路径的起点和终点都是还没有匹配过的点,并且路径经过的连线是一条没被匹配、一条已经匹配过,再下一条又没匹配这样交替地出现。找到这样的路径后,显然路径里没被匹配的连线比已经匹配了的连线多一条,于是修改匹配图,把路径里所有匹配过的连线去掉匹配关系,把没有匹配的连线变成匹配的,这样匹配数就比原来多1个。不断执行上述操作,直到找不到这样的路径为止。