1 /*  2    做网络流的题建图真的是太重要了！  3    本题是将人所在的位置和房子所在的位置建立边的联系，其中man到house这一条边的流量为 1， 费用为两者的距离  4    而方向边的流量为 0， 费用为正向边的相反数（也就是沿着反向边进行增广时，费用要减少，更改先前错误的选择）   5    最后增加一个源点和一个汇点完毕（源点映射到man， house映射到汇点， 费用为0， 流量为1）   6 */  7 #include<iostream>   8 #include<cmath>  9 #include<cstdio> 10 #include<cstring> 11 #include<queue> 12 #define Max 0x3f3f3f3f 13 #define N 205 14 using namespace std; 15  16 class node 17 { 18 public:   19    int x, y; 20 }; 21  22 node xyM[N]; 23 node xyH[N]; 24 int cost[N][N], cap[N][N]; 25 int cntM, cntH; 26 int pre[N*2], dist[N*2], vis[N*2], n, m; 27  28 void addE(int i, int j, int ct, int cp) 29 { 30     cost[i][j]=ct; 31     cap[i][j]=cp; 32     cost[j][i]=-ct; 33     //cap[j][i]=0; 34 } 35  36 int s, t, minCost; 37  38 void buildMap() 39 { 40    int i, j; 41    memset(cap, 0, sizeof(cap)); 42    s=0; t=cntM+cntH+1; 43    for(i=0; i<cntM; ++i) 44      addE(0, i+1, 0, 1);   45    for(i=0; i<cntH; ++i) 46      addE(cntM+i+1, t, 0, 1); 47    for(i=0; i<cntM; ++i) 48      for(j=0; j<cntH; ++j) 49        addE(i+1, cntM+j+1, abs(xyM[i].x-xyH[j].x)+abs(xyM[i].y-xyH[j].y), 1); 50 } 51  52 queue<int>q; 53  54 int spfa() 55 { 56     int u, v; 57     memset(dist, 0x3f, sizeof(dist)); 58     dist[0]=0; 59     q.push(0); 60     vis[0]=1; 61     while(!q.empty()) 62     { 63         u=q.front(); 64         q.pop(); 65         vis[u]=0; 66         for(v=0; v<=t; ++v) 67           if(cap[u][v]>0 && dist[v]>dist[u]+cost[u][v]) 68           { 69               dist[v]=dist[u]+cost[u][v]; 70               pre[v]=u; 71               if(!vis[v]) 72               { 73                     vis[v]=1; 74                     q.push(v); 75           } 76       } 77     } 78     if(dist[t]==Max) 79       return 0; 80     return 1; 81 } 82  83 void updateEdge() 84 {  85    int u, minFlow=Max; 86    for(u=t; u!=s; u=pre[u])//通过最短路径寻找这条路径上的最小流量  87       if(cap[pre[u]][u]<minFlow) 88         minFlow=cap[pre[u]][u]; 89     for(u=t; u!=s; u=pre[u]) 90     { 91         cap[pre[u]][u]-=minFlow; 92         cap[u][pre[u]]+=minFlow; 93         minCost+=cost[pre[u]][u]; 94     } 95 } 96  97 int main() 98 { 99    int i, j;100    char c;101    while(scanf("%d%d", &n, &m) && (n||m))102    {103        cntM=cntH=0;104        minCost=0;105        for(i=1; i<=n; ++i)106          {107            getchar();108        for(j=1; j<=m; ++j)109              {110             scanf("%c", &c);111             if(c==‘m‘)112             {113                xyM[cntM].x=i;114                xyM[cntM++].y=j;115         }116         else if(c==‘H‘)117         {118            xyH[cntH].x=i;119                xyH[cntH++].y=j;120         }121          }122         }123         buildMap();124         while(spfa())125           updateEdge();126         printf("%d\n", minCost);127    }128    return 0;129 }