KM 求權值最小的完美匹配
Going Home Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 17309 Accepted: 8824
Description
On a grid map there are n little men and n houses. In each unit time, every little man can move one unit step, either horizontally, or vertically, to an adjacent point. For each little man, you need to pay a $1 travel fee for every step he moves, until he enters a house. The task is complicated with the restriction that each house can accommodate only one little man.Input
There are one or more test cases in the input. Each case starts with a line giving two integers N and M, where N is the number of rows of the map, and M is the number of columns. The rest of the input will be N lines describing the map. You may assume both N and M are between 2 and 100, inclusive. There will be the same number of 'H's and 'm's on the map; and there will be at most 100 houses. Input will terminate with 0 0 for N and M.Output
For each test case, output one line with the single integer, which is the minimum amount, in dollars, you need to pay.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
Source
Pacific Northwest 2004[Submit] [Go Back] [Status] [Discuss]
#include#include #include #include using namespace std; const int maxn=2500; const int INF=0x3f3f3f3f; int n,m; char mp[120][120]; struct POINT { int x,y; }human[maxn],house[maxn]; int nx,ny; int g[maxn][maxn]; int linker[maxn],lx[maxn],ly[maxn]; int slack[maxn]; bool visx[maxn],visy[maxn]; bool dfs(int x) { visx[x]=true; for(int y=0;y tmp) slack[y]=tmp; } return false; } int KM() { memset(linker,-1,sizeof(linker)); memset(ly,0,sizeof(ly)); for(int i=0;i lx[i]) lx[i]=g[i][j]; } for(int x=0;x slack[i]) d=slack[i]; for(int i=0;i