POJ-2195 Going Home---KM算法求最小权值匹配(存负边)

题目链接:

https://vjudge.net/problem/POJ-2195

题目大意:

给定一个N*M的地图,地图上有若干个man和house,且man与house的数量一致。man每移动一格需花费$1(即单位费用=单位距离),一间house只能入住一个man。现在要求所有的man都入住house,求最小费用。

思路:

KM算法传送门: 理解篇    运用篇

每个man和house建立带权二分图,曼哈顿距离就是边的值,这里要求最小费用,也就是二分图最小权值匹配,但是KM算法求的是二分图最大权值匹配,所以此处用边的负数求最优匹配,求出来的答案的负数就是最小权匹配。

注意:题目说house最多100,但是没有说明man的范围,所以man应该最多100*100。

应该用house为二分图的X部,因为算法复杂度和X部点数有关,所以用点数少的house为X部

因为存的是负数,在预处理X部的顶标值初始化应该是-INF,不能是0

剩下的就是模板啦

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxx = + ;//house的上限
const int maxy = + ;//man的上限
const int INF = 0x3f3f3f3f;
int cntx, cnty;//X部的点的数目,Y部点的数目
bool visx[maxx], visy[maxy];//是否加入增广路
int wx[maxx], wy[maxy];//顶标值
int cx[maxx], cy[maxy];//匹配的点
int minz;//顶标值和边权最小的差值
int Map[maxx][maxy];//保存边 bool dfs(int u)
{
visx[u] = ;
for(int v = ; v <= cnty; v++)
{
if(!visy[v])//还未加入增广路
{
int t = wx[u] + wy[v] - Map[u][v];
//计算边权和顶标之差,为0表示是相等子图
if(t == )
{
visy[v] = ;
if(cy[v] == - || dfs(cy[v]))//还未匹配或者反向找到增广路
{
cy[v] = u;
cx[u] = v;
//cout<<u<<"v"<<v<<endl;
return ;
}
}
else if(t > )minz = min(minz, t);
}
}
return ;
} int KM()
{
memset(cx, -, sizeof(cx));
memset(cy, -, sizeof(cy));
memset(wx, -INF, sizeof(wx));//注意,这里存的是负边,所以初始化必须是负无穷
memset(wy, , sizeof(wy));
for(int i = ; i <= cntx; i++)//预处理出X部的顶标值
{
for(int j = ; j <= cnty; j++)
{
wx[i] = max(wx[i], Map[i][j]);
//cout<<wx[i]<<endl;
}
}
for(int i = ; i <= cntx; i++)
{
while()
{
minz = INF;
memset(visx, , sizeof(visx));
memset(visy, , sizeof(visy));
if(dfs(i))break; for(int j = ; j <= cntx; j++)
if(visx[j])wx[j] -= minz;
for(int j = ; j <= cnty; j++)
if(visy[j])wy[j] += minz;
}
}
int ans = ;
for(int i = ; i <= cntx; i++)
if(cx[i] != -)ans += Map[i][cx[i]];
return ans;
}
struct node
{
int x, y;
node(){}
node(int x, int y):x(x), y(y){}
};
node house[maxx], man[maxy];
char M[][];
int main()
{
int n, m;
while(cin >> n >> m && (n && m))
{
cntx = cnty = ;
for(int i = ; i < n; i++)//读图
{
cin >> M[i];
for(int j = ; j < m; j++)
{
if(M[i][j] == 'H')house[++cntx] = node(i, j);
else if(M[i][j] == 'm')man[++cnty] = node(i, j);
}
} for(int i = ; i <= cntx; i++)//建图
{
for(int j = ; j <= cnty; j++)
{
Map[i][j] = -abs(house[i].x - man[j].x) - abs(house[i].y - man[j].y);
}
}
cout<<(-KM())<<endl;
}
return ;
}
上一篇:TFS二次开发01——TeamProjectsPicher


下一篇:最小生成树 --- 求最小权值、MST