|
Posted on 2010-08-21 18:01 acronix 阅读(608) 评论(2) 编辑 收藏 引用 所属分类: hzshuai解题报告 、 hzshuai解题中算法总结
以下为KM算法模板:
//boj1080 /*=================================================*\ | 二分图最佳匹配(kuhn munkras 算法O(m*m*n)) | 邻接距阵形式,复杂度O(m*m*n) 返回最佳匹配值,传入二分图大小n,m | 邻接距阵map,表示权, match返回一个最佳匹配,未匹配顶点 | match值为-1, 一定注意m<=n,否则循环无法终止,最小权匹配可将权值 | 取相反数
\*==================================================*/ #include <cstdio> #include <memory.h> const int inf = 0x7fffffff;
int map[25][25],n,lx[25],ly[25],match[25]; bool x[25],y[25];
/************* 寻找增广路******************************/ bool SearchPath(int u) { x[u] = true; //x注意标记已匹配 for (int v = 1; v <= n; v++) if(!y[v] && ly[v] + lx[u] == map[u][v]) { y[v] = true; if (match[v] == -1 || SearchPath(match[v])) { match[v] = u; return true; } } return false; }
int KM() { int i,j,k,d; for (i = 1; i <= n; i++) while(1) { memset(x,false,sizeof(x)); memset(y,false,sizeof(y)); if (SearchPath(i)) //找到完美匹配子图 break; d = inf; for (j = 1; j <= n; j++) if (x[j]) { for (k = 1; k <= n; k++) if (!y[k]) if (d > lx[j] + ly[k] - map[j][k]) d = lx[j] + ly[k] - map[j][k]; } for (j = 1; j <= n;j ++) //降低阶梯 { if (x[j]) lx[j] -= d; if (y[j]) ly[j] += d; } } int ans = 0; for (i = 1; i <= n; i++) ans += map[match[i]][i]; return ans; }
/**********************************************/
int main() { int i,j,k,v; while (scanf("%d",&n) != EOF) { for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) { scanf("%d", &v); map[i][j] = -v; } /************** 顶标坐标初始化 ly[i]初始化为0,lx[i]初始化为与i相邻边权最大的值 ********************************/ memset(ly,0,sizeof(ly)); for (i = 1; i <= n; i++) { lx[i] = -inf; for (j = 1; j <= n; j ++) if (lx[i] < map[i][j]) lx[i] = map[i][j]; } memset(match,-1,sizeof(match)); printf("%d\n",-KM()); /******************************************/
} return 0; }
同时BOJ 1084也是一个很裸的求二分图最佳匹配的问题。
Feedback
# re: KM最佳匹配的模板 回复 更多评论
2012-05-25 09:59 by
您好,
读了您的博文受益良多。
在Boj 1080的中,你说,如果“求解最小权值完美匹配,可以将权值求相反数”。 我在这个地方有一些疑惑?
如果求相反数的话,可行顶标的修改步骤中d的取值是不是应该变为选最大?可行顶标的修改是不是S集合中点+d,而T集合中点-d? 还是仍然按照原始步骤即可?
另外,如果“求取最小权值完美匹配”,可不可以通过将权值取“倒数”的方法来实现。
初涉二分图匹配算法,万望博主不吝赐教
# re: KM最佳匹配的模板 回复 更多评论
2012-05-25 10:01 by
貌似。boj2195就是最小权值完美匹配..
|