最小费用最大流，EK中的BFS改成SPFA。。。
建图拿人和房子建，费用是人和房子坐标差值，加源点和汇点，求最小费用最大流即可。
我WA的厉害 = =。。。少加了句cost[to][from] = -cost[from][to];。。。
#include <cstdio> #include <cstdlib> #include <iostream> #include <string.h> #include <queue> #include <math.h> #include <limits.h> #define MAX 210 using namespace std; typedef struct HOUSE{ int x,y; int num; }HOUSE; HOUSE h[MAX],m[MAX]; int n,M; int cap[MAX][MAX]; int cost[MAX][MAX]; int EKarpSPFA(int s,int t) { int flow[MAX][MAX],a,c,i,dis[MAX]; int pre[MAX],u,v; queue <int> Q; int inq[MAX]; c = 0; memset(flow,0,sizeof(flow)); while(1) { for(i=s; i<=t; i++) dis[i] = INT_MAX; dis[s] = 0; memset(inq,0,sizeof(inq)); Q.push(s); inq[s] = 1; while( !Q.empty() ) { u = Q.front(); Q.pop(); inq[u] = 0; for(v=s; v<=t; v++) if( cap[u][v] > flow[u][v] && dis[v] > dis[u] + cost[u][v] ) { dis[v] = dis[u] + cost[u][v]; pre[v] = u; if( !inq[v] ) { Q.push(v); inq[v] = 1; } } } if( dis[t] == INT_MAX ) break; a = INT_MAX; for(u=t; u!=s; u=pre[u]) if( cap[pre[u]][u] - flow[pre[u]][u] < a ) a = cap[pre[u]][u] - flow[pre[u]][u]; for(u=t; u!=s; u=pre[u]) { flow[pre[u]][u] += a; flow[u][pre[u]] -= a; } c += dis[t]*a; } return c; } int main() { int i,house,man,k,from,to,ans; char str[MAX]; while( scanf("%d%d",&n,&M) != EOF && n && M ) { memset(cap,0,sizeof(cap)); memset(cost,0,sizeof(cost)); memset(h,'/0',sizeof(h)); memset(m,'/0',sizeof(m)); house = man = 1; for(i=0; i<n; i++) { scanf("%s",str); for(k=0; k<M; k++) { if( str[k] == 'H' ) { h[house].x = i; h[house].num = house; h[house++].y = k; } if( str[k] == 'm' ) { m[man].x = i; m[man].num = man; m[man++].y = k; } } } for(i=1; i<house; i++) { cap[i][house+man-1] = 1; for(k=1; k<man; k++) { from = k + house - 1; to = i; cap[from][to] = 1; cost[from][to] = abs( m[k].x - h[i].x ) + abs( m[k].y - h[i].y ); cost[to][from] = -cost[from][to]; } } for(k=1; k<man; k++) cap[0][k+house-1] = 1; ans = EKarpSPFA(0,man+house-1); printf("%d/n",ans); } return 0; }
