Posted on 2010-08-21 17:51
acronix 阅读(203)
评论(0) 编辑 收藏 引用 所属分类:
hzshuai解题报告
题意：给一个n*m的方块矩阵，人和房子散乱的分布在上边，人数和房子数相等，现在要人都一动到房子里去，一人一房，人每一动一格花费为 1，问要全部人到达各自的房子的最少花费。
分析：转化为二分图最佳匹配，一边为人，一边为房子，他们之间的边权为负花费。再使用KM算法求得边权为负的最佳匹配，再取反极为最小花费了，轻松解决。cpp代码：
#include <cstdio>
#include <memory.h>
#include <algorithm>
const int inf = -0x7fffffff;
struct Point{
int x,y;
}h[105],m[105];
int cn,cm,cnth,cntm,map[105][105];
bool x[105],y[105];
int match[105],lx[105],ly[105],len;
bool SearchPath(int u)
{
x[u] = true;//注意标记
for (int v = 1; v <= len; v++)
if (lx[u]+ly[v] == map[u][v] && !y[v])
{
y[v] = true;
if (match[v] == -1 || SearchPath(match[v]))
{
match[v] = u;
return true;
}
}
return false;
}
int KM()
{
int i,j,k;
int d;
memset(ly,0,sizeof(ly));
for (i = 1; i <= len; i++)
{
lx[i] = inf;
for (j = 1; j <= len; j ++)
if (lx[i] > map[i][j])
lx[i] = map[i][j];
}
memset(match,-1,sizeof(match));
for (i = 1; i <= len; i++)
while (1)
{
memset(x,false,sizeof(x));
memset(y,false,sizeof(y));
if (SearchPath(i))
break;
d = -inf;
for (j = 1; j <= len; j++)
if (x[j])
{
for (k = 1; k <= len; 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 <= len; j ++)
{
if (x[j]) lx[j] -= d;
if (y[j]) ly[j] += d;
}
}
int ans = 0;
for (i = 1; i <= len ; i++)
ans += map[match[i]][i];
return ans;
}
int main()
{
int i,j,k;
char chr[105];
while (scanf("%d %d",&cn,&cm) && cn + cm != 0)
{
cnth = cntm = 0;
for (i = 1; i <= cn; i++)
{
scanf("%s",chr);
for (j = 1; j <= cm; j++)
{
map[i][j] = 0;
if (chr[j-1] == 'H')
{
cnth++;
h[cnth].x = i; h[cnth].y = j;
}
if (chr[j-1] == 'm')
{
cntm++;
m[cntm].x = i; m[cntm].y = j;
}
}
}
len = cnth;
for (i = 1; i <= len; i ++)
for (j = 1; j <= len; j++)
map[i][j] = -(abs(h[i].x - m[j].x) + abs(h[i].y - m[j].y));
printf("%d\n",-KM());
}
return 0;
}