Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4223 Accepted Submission(s): 2178
#include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; const int INF = 999999999; const int N = 205; ///most 100 person and house const int M = N*N*2; struct Edge{ int u,v,cap,cost,next; }edge[M]; int head[N],tot,low[N],pre[N]; int total ; bool vis[N]; void addEdge(int u,int v,int cap,int cost,int &k){ edge[k].u=u,edge[k].v=v,edge[k].cap = cap,edge[k].cost = cost,edge[k].next = head[u],head[u] = k++; edge[k].u=v,edge[k].v=u,edge[k].cap = 0,edge[k].cost = -cost,edge[k].next = head[v],head[v] = k++; } void init(){ memset(head,-1,sizeof(head)); tot = 0; } bool spfa(int s,int t,int n){ memset(vis,false,sizeof(vis)); for(int i=0;i<=n;i++){ low[i] = (i==s)?0:INF; pre[i] = -1; } queue<int> q; q.push(s); while(!q.empty()){ int u = q.front(); q.pop(); vis[u] = false; for(int k=head[u];k!=-1;k=edge[k].next){ int v = edge[k].v; if(edge[k].cap>0&&low[v]>low[u]+edge[k].cost){ low[v] = low[u] + edge[k].cost; pre[v] = k; ///v为终点对应的边 if(!vis[v]){ vis[v] = true; q.push(v); } } } } if(pre[t]==-1) return false; return true; } int MCMF(int s,int t,int n){ int mincost = 0,minflow,flow=0; while(spfa(s,t,n)) { minflow=INF+1; for(int i=pre[t];i!=-1;i=pre[edge[i].u]) minflow=min(minflow,edge[i].cap); flow+=minflow; for(int i=pre[t];i!=-1;i=pre[edge[i].u]) { edge[i].cap-=minflow; edge[i^1].cap+=minflow; } mincost+=low[t]*minflow; } total=flow; return mincost; } int n,m,a,b; char graph[N][N]; struct House{ int x,y; }h[N]; struct Person{ int x,y; }p[N]; int main() { while(scanf("%d%d",&n,&m)!=EOF,n+m){ init(); a=0,b=0; for(int i=0;i<n;i++){ scanf("%s",graph[i]); for(int j=0;j<m;j++){ if(graph[i][j]==‘H‘){ h[++a].x = i,h[a].y = j; } if(graph[i][j]==‘m‘){ p[++b].x = i,p[b].y = j; } } } int src = 0,des = a+b+1; for(int i=1;i<=a;i++){ for(int j=1;j<=b;j++){ int D = abs(h[i].x-p[j].x)+abs(h[i].y-p[j].y); addEdge(i,j+a,1,D,tot); } } for(int i=1;i<=a;i++){ addEdge(src,i,1,0,tot); } for(int i=1;i<=b;i++){ addEdge(i+a,des,1,0,tot); } int mincost = MCMF(src,des,a+b+2); printf("%d\n",mincost); } return 0; }
原文:http://www.cnblogs.com/liyinggang/p/5727559.html