|
|
Posted on 2010-08-21 18:01 acronix 阅读(620) 评论(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;
}
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就是最小权值完美匹配..
|