给定一个N*M的地图,地图上有若干个man和house,且man与house的数量一致。man每移动一格需花费$1(即单位费用=单位距离),一间house只能入住一个man。现在要求所有的man都入住house,求最小费用。
建图:
s连每个房间 c为1 cost为0
每个人连t c为1 cost为0
每个房间连每个人 c为1 cost为abs(x)+abs(y)
然后跑最小费用流
算法一次敲对了,数组开小了,坑爹啊
#include<cstdio> #include<queue> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int n_max=205; const int m_max=21505; const int inf=1<<30; struct edge { int u,v,cap,cost,pre; void add(int pu,int pv,int pcap,int pcost,int ppre) { u=pu; v=pv; cap=pcap; cost=pcost; pre=ppre; } }e[m_max]; int ne; int head[n_max]; int min_cost,max_flow; struct point { int x,y; void add(int xx,int yy) { x=xx; y=yy; } }hou[n_max],man[n_max]; int nhou,nman; void init() { ne=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int cap,int cost) { e[ne].add(u,v,cap,cost,head[u]); head[u]=ne++; e[ne].add(v,u,0,-cost,head[v]); head[v]=ne++; } void min_cost_max_flow(int s,int t) { min_cost=max_flow=0; while(true) { int p[n_max]; memset(p,-1,sizeof(p)); int d[n_max]; int i; for(i=0;i<n_max;i++) { d[i]=inf; } d[s]=0; bool inq[n_max]; memset(inq,0,sizeof(inq)); queue<int> q; q.push(s); inq[s]=true; int u,v; while(!q.empty()) { u=q.front(); q.pop(); inq[u]=false; for(i=head[u];i!=-1;i=e[i].pre) { v=e[i].v; if(e[i].cap&&d[v]>d[u]+e[i].cost) { d[v]=d[u]+e[i].cost; p[v]=i; if(!inq[v]) { q.push(v); inq[v]=true; } } } } if(d[t]==inf) { break; } int nmin=inf; for(i=p[t];i!=-1;i=p[e[i].u]) { nmin=min(nmin,e[i].cap); } for(i=p[t];i!=-1;i=p[e[i].u]) { e[i].cap -= nmin; e[i^1].cap += nmin; } min_cost += d[t]*nmin; max_flow += nmin; } } int main() { char str[110]; int n,m,s,t; while(~scanf("%d%d",&n,&m)) { nhou=nman=0; if(n+m==0) { break; } int i,j; for(i=0;i<n;i++) { scanf("%s",str); for(j=0;j<m;j++) { if(str[j]=='H') { hou[++nhou].add(i,j); } else if(str[j]=='m') { man[++nman].add(i,j); } } } s=0; t=nhou+nman+1; init(); for(i=1;i<=nhou;i++) { for(j=1;j<=nman;j++) { int cost=fabs(hou[i].x-man[j].x) + fabs(hou[i].y-man[j].y); addedge(i,nhou+j,1,cost); } } for(i=1;i<=nhou;i++) { addedge(s,i,1,0); } for(j=1;j<=nman;j++) { addedge(nhou+j,t,1,0); } min_cost_max_flow(s,t); printf("%d\n",min_cost); } return 0; }