题意：住房终于包分配了！现有一张地图，人用m表示，房子用H表示。人每次上下左右走一格，到房子的距离为走的步数。现要使求一种方案，使得所有人到自己房子距离之和最少。输出最小距离和。

解：套路建图，人到房子花费为距离，流量随便，只要保证所有人到所有房子机会均等就行。这里我全设为1。写的时候脑子一抽，把房子当障碍物，于是写了个bfs求距离，实际上只要算曼哈顿距离戒行了。。。。。就当练bfs了。

代码：

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <queue>
  4 using namespace std;
  5 #define maxx 1000005
  6 #define maxm 100005
  7 #define maxn 505
  8 #define inf 0x3f3f3f3f
  9 #define ll long long
 10 int n,m,h1,h2;
 11 char s[maxn][maxn];
 12 int d[maxn][maxn];
 13 int xx[4]={0,1,0,-1};
 14 int yy[4]={1,0,-1,0};
 15 int vis[maxn][maxn];
 16 struct node{
 17     int x,y,step;
 18 }t;
 19 
 20 int head[maxn],cnt;
 21 struct Edge{
 22     int u,v,w,next,flow;
 23 }edge[maxm];
 24 int st,ed;
 25 int dis[maxn],incf[maxn],pre[maxn],inque[maxn];
 26 int maxflow,mincost;
 27 void init(){
 28     memset(head,-1,sizeof(head));
 29     maxflow=mincost=0;
 30     cnt=0;
 31 }
 32 void add(int u,int v,int flow,int cost){
 33     edge[cnt].u=u;
 34     edge[cnt].w=cost;
 35     edge[cnt].v=v;
 36     edge[cnt].flow=flow;
 37     edge[cnt].next=head[u];
 38     head[u]=cnt++;
 39 }
 40 void addEdge(int u,int v,int flow,int cost){
 41     add(u,v,flow,cost);
 42     add(v,u,0,-cost);
 43 }
 44 int spfa(){
 45     queue<int>q;
 46     memset(dis,0x3f,sizeof(dis));
 47     memset(inque,0,sizeof(inque));
 48     q.push(st); dis[st]=0; inque[st]=1; incf[st]=inf;
 49     while(!q.empty()){
 50         int u=q.front();q.pop();
 51         inque[u]=0;
 52         for(int i=head[u];~i;i=edge[i].next){
 53             if(!edge[i].flow)    continue;
 54             int v=edge[i].v;
 55             if(dis[v]>dis[u]+edge[i].w){
 56                 dis[v]=dis[u]+edge[i].w;
 57                 incf[v]=min(incf[u],edge[i].flow);
 58                 pre[v]=i;
 59                 if(!inque[v]){
 60                     q.push(v);
 61                     inque[v]=1;
 62                 }
 63             }
 64         }
 65     }
 66     if(dis[ed]==inf)
 67         return 0;
 68     return 1;
 69 }
 70 void MCMF(){
 71     while(spfa()){
 72         int x=ed;
 73         maxflow+=incf[ed];
 74         mincost+=dis[ed]*incf[ed];
 75         int i;
 76         while(x!=st){
 77             i=pre[x];
 78             edge[i].flow-=incf[ed];
 79             edge[i^1].flow+=incf[ed];
 80             x=edge[i^1].v;
 81         }
 82     }
 83 }
 84 
 85 void bfs(int x,int y){
 86     queue<node> q;
 87     memset(vis,0,sizeof vis);
 88     t.x=x,t.y=y,t.step=0;
 89     q.push(t);
 90     vis[x][y]=1;
 91     int cnt=0;
 92     while(!q.empty()){
 93         node now=q.front();
 94         q.pop();
 95         for(int i=0;i<4;i++){
 96             int tx=now.x+xx[i],ty=now.y+yy[i];
 97             if(tx<0||tx>=n||ty<0||ty>=m||vis[tx][ty])
 98                 continue;
 99             vis[tx][ty]=1;
100             if(s[tx][ty]=='H'){
101                 addEdge(d[x][y],d[tx][ty],1,now.step+1);
102                 cnt++;
103                 if(cnt==h1)
104                     return;
105             }
106             t.x=tx,t.y=ty,t.step=now.step+1;
107             q.push(t);
108         }
109     }
110 }
111 signed main(){
112     while(~scanf("%d%d",&n,&m)){
113         init();
114         if(n==0&&m==0)
115             break;
116         memset(d,0,sizeof d);
117         for(int i=0;i<n;i++)
118             scanf("%s",s[i]);
119         h1=0,h2=200;
120         st=401,ed=402;
121         for(int i=0;i<n;i++)
122             for(int j=0;j<m;j++) {
123                 if (s[i][j] == 'm')
124                     d[i][j]=++h1;
125                 if(s[i][j]=='H')
126                     d[i][j]=++h2;
127             }
128         for(int i=0;i<n;i++)
129             for(int j=0;j<m;j++)
130                 if(s[i][j]=='m')
131                     bfs(i,j);
132         for(int i=1;i<=h1;i++)
133             addEdge(st,i,1,0);
134         for(int i=201;i<=h2;i++)
135             addEdge(i,ed,1,0);
136         MCMF();
137         printf("%d\n",mincost);
138     }
139     return 0;
140 }

View Code