题意：一个矩阵中不同位置给出n个人，和n个房子，求解n个人分别回到n个房子的最小时间花费。
思路：最大权匹配，可用最小费用流，km算法求解。
最小费用流算法：
View Code
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<algorithm> 5 using namespace std; 6 #define inf 0x3f3f3f3f 7 #define N 100010 8 #define M N*10 9 struct edge{ 10 int a,next,b,cap,flow,cost; 11 }e[M]; 12 struct point{ 13 int x,y; 14 }m[N],h[N]; 15 int pre[N],q[N*2],in[N],low[N],dist[N],p[N]; 16 int cnt,S,T; 17 void add(int a,int b,int cap,int cost) 18 { 19 edge es={a,pre[a],b,cap,0,cost}; 20 e[cnt]=es; 21 pre[a]=cnt++; 22 } 23 bool spfa() 24 { 25 int rear=0,tail=1; 26 q[0]=S; 27 memset(low,0,sizeof(low)); 28 memset(in,0,sizeof(in)); 29 for(int i=S;i<=T;i++) 30 dist[i]=inf; 31 low[S]=inf;dist[S]=0; 32 in[S]=1; 33 while(rear<tail) 34 { 35 int u=q[rear++]; 36 in[u]=0; 37 for(int edg=pre[u];edg!=0;edg=e[edg].next) 38 { 39 int v=e[edg].b; 40 if(dist[v]>dist[u]+e[edg].cost&&e[edg].cap>e[edg].flow) 41 { 42 p[v]=edg; 43 dist[v]=dist[u]+e[edg].cost; 44 if(!in[v]){ 45 q[tail++]=v; 46 in[v]=1; 47 } 48 low[v]=min(low[u],e[edg].cap-e[edg].flow); 49 if(v==T)break; 50 } 51 } 52 } 53 return low[T]!=0; 54 } 55 int dfs() 56 { 57 int tf=0; 58 while(spfa()) 59 { 60 tf+=low[T]*dist[T]; 61 for(int x=p[T];x!=0;x=p[e[x].a]) 62 { 63 e[x].flow+=low[T]; 64 e[x^1].flow-=low[T]; 65 } 66 } 67 return tf; 68 } 69 int main() 70 { 71 int r,c; 72 while(scanf("%d%d",&r,&c)!=EOF) 73 { 74 memset(pre,0,sizeof(pre)); 75 cnt=2; 76 int hc=1,mc=1; 77 if(r==0&&c==0)break; 78 for(int i=1;i<=r;i++) 79 { 80 getchar(); 81 for(int j=1;j<=c;j++) 82 { 83 char ch; 84 scanf("%c",&ch); 85 if(ch=='m'){ 86 m[mc].x=i; 87 m[mc++].y=j; 88 } 89 else if(ch=='H') 90 { 91 h[hc].x=i; 92 h[hc++].y=j; 93 } 94 } 95 } 96 S=0;T=mc+hc-1; 97 for(int i=1;i<mc;i++) 98 for(int j=1;j<hc;j++) 99 { 100 int len=abs(m[i].x-h[j].x)+abs(m[i].y-h[j].y); 101 add(i,j+mc-1,1,len); 102 add(j+mc-1,i,0,-len); 103 } 104 for(int i=1;i<mc;i++) 105 { 106 add(S,i,1,0); 107 add(i,S,0,0); 108 } 109 for(int i=1;i<hc;i++) 110 { 111 add(i+mc-1,T,1,0); 112 add(T,i+mc-1,0,0); 113 } 114 printf("%d\n",dfs()); 115 } 116 }
KM算法实现：
View Code
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<algorithm> 5 using namespace std; 6 #define inf 0x3f3f3f3f 7 #define N 1010 8 int d; 9 int net[N][N],x[N],y[N],lx[N],ly[N],link[N]; 10 struct point{ 11 int x,y; 12 }m[N],h[N]; 13 bool dfs(int u,int mc) 14 { 15 x[u]=1; 16 for(int v=1;v<mc;v++) 17 { 18 if(y[v])continue; 19 int t=lx[u]+ly[v]-net[u][v]; 20 if(!t) 21 { 22 y[v]=1; 23 if(!link[v]||dfs(link[v],mc)) 24 { 25 link[v]=u; 26 return true; 27 } 28 } 29 else d=min(d,t); 30 } 31 return false; 32 } 33 int km(int mc,int hc) 34 { 35 memset(ly,0,sizeof(ly)); 36 for(int i=0;i<mc;i++) 37 lx[i]=inf; 38 for(int i=1;i<mc;i++) 39 { 40 while(1) 41 { 42 d=inf; 43 memset(x,0,sizeof(x)); 44 memset(y,0,sizeof(y)); 45 if(dfs(i,mc))break; 46 for(int j=1;j<mc;j++) 47 { 48 if(x[j])lx[j]-=d; 49 if(y[j])ly[j]+=d; 50 } 51 } 52 } 53 int sum=0; 54 for(int i=1;i<mc;i++) 55 sum+=lx[i]+ly[i]; 56 return sum; 57 } 58 int main() 59 { 60 int r,c; 61 while(scanf("%d%d",&r,&c)) 62 { 63 if(r==0&&c==0)break; 64 int mc=1,hc=1; 65 for(int i=1;i<=r;i++) 66 { 67 getchar(); 68 for(int j=1;j<=c;j++) 69 { 70 char ch; 71 scanf("%c",&ch); 72 if(ch=='m') 73 { 74 m[mc].x=i; 75 m[mc++].y=j; 76 } 77 else if(ch=='H') 78 { 79 h[hc].x=i; 80 h[hc++].y=j; 81 } 82 } 83 } 84 memset(net,0,sizeof(net)); 85 memset(link,0,sizeof(link)); 86 for(int i=1;i<mc;i++) 87 { 88 for(int j=1;j<hc;j++) 89 { 90 net[i][j]=500-(abs(m[i].x-h[j].x)+abs(m[i].y-h[j].y)); 91 } 92 } 93 printf("%d\n",500*(mc-1)-km(mc,hc)); 94 } 95 return 0; 96 }