本文主要是介绍用二分图模型解决poj 2195,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
之前这道题用了费用流来解决,这次用了二分图最佳匹配来解决。
不过,用二分图最佳匹配解决这道题时,要注意题目要求花费最小,所以是求权值之和最小的最佳匹配。要用一个大数减去原有权值作为新的权值,最后输出答案时,要注意还原真正的权值。
通过这道题,也可以发现费用流与二分图最佳匹配之间有所关联,而且就这道题来看,二分图的代码量会小于费用流的代码量,所以尽可能采用二分图模型来解决问题可能会简单些。
代码(C++):
#include <cstdlib>
#include <iostream>
#include <cmath>#define MAX 150
#define INF (1<<30)
using namespace std;//#define LOCALtypedef pair<int,int> pii;
pii array_h[MAX],array_m[MAX];int w[MAX][MAX],lx[MAX],ly[MAX],cy[MAX],vx[MAX],vy[MAX];bool match(int u,int n)
{int i;vx[u]=true;for(i=0;i<n;i++){if(lx[u]+ly[i]==w[u][i]&&!vy[i]){vy[i]=true; if(cy[i]==-1||match(cy[i],n)){cy[i]=u;return true; } } } return false;
}void update(int n)
{int i,j,d;d=INF;for(i=0;i<n;i++) if(vx[i]){for(j=0;j<n;j++) if(!vy[j]){d=min(d,lx[i]+ly[j]-w[i][j]); } } for(i=0;i<n;i++){if(vx[i]) lx[i]-=d;if(vy[i]) ly[i]+=d; }
}int km(int n)
{int i,j,ans;for(i=0;i<n;i++){lx[i]=-INF;ly[i]=0;cy[i]=-1;for(j=0;j<n;j++) lx[i]=max(lx[i],w[i][j]); }for(i=0;i<n;i++){while(1){memset(vx,false,sizeof(vx));memset(vy,false,sizeof(vy));if(match(i,n)) break;else update(n); } }ans=0;for(i=0;i<n;i++) ans+=w[cy[i]][i];return ans;
}int main(int argc, char *argv[])
{
#ifdef LOCAL freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#endifint n,m,a,b,i,j,fee,max;char ch;while(scanf("%d %d",&n,&m)&&n+m!=0){a=b=0; for(i=0;i<n;i++){getchar(); for(j=0;j<m;j++){scanf("%c",&ch);if(ch=='H') array_h[a++]=make_pair(i,j);else if(ch=='m') array_m[b++]=make_pair(i,j); } }max=n+m;for(i=0;i<b;i++){for(j=0;j<a;j++){fee=abs(array_m[i].first-array_h[j].first)+abs(array_m[i].second-array_h[j].second); w[i][j]=max-fee; } } printf("%d\n",max*a-km(a)); }system("PAUSE");return EXIT_SUCCESS;
}
题目( http://poj.org/problem?id=2195):
Time Limit: 1000MS | Memory Limit: 65536K | |
Description
Your task is to compute the minimum amount of money you need to pay in order to send these n little men into those n different houses. The input is a map of the scenario, a '.' means an empty space, an 'H' represents a house on that point, and am 'm' indicates there is a little man on that point.
You can think of each point on the grid map as a quite large square, so it can hold n little men at the same time; also, it is okay if a little man steps on a grid with a house without entering that house.
Input
Output
Sample Input
2 2 .m H. 5 5 HH..m ..... ..... ..... mm..H 7 8 ...H.... ...H.... ...H.... mmmHmmmm ...H.... ...H.... ...H.... 0 0
Sample Output
2 10 28
这篇关于用二分图模型解决poj 2195的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!