本文共 3046 字，大约阅读时间需要 10 分钟。

/*   做网络流的题建图真的是太重要了！   本题是将人所在的位置和房子所在的位置建立边的联系，其中man到house这一条边的流量为 1， 费用为两者的距离   而方向边的流量为 0， 费用为正向边的相反数（也就是沿着反向边进行增广时，费用要减少，更改先前错误的选择）    最后增加一个源点和一个汇点完毕（源点映射到man， house映射到汇点， 费用为0， 流量为1） */#include
    
      #include
     
      #include
      
       #include
       
        #include
        
         #define Max 0x3f3f3f3f#define N 205using namespace std;class node{public:     int x, y;};node xyM[N];node xyH[N];int cost[N][N], cap[N][N];int cntM, cntH;int pre[N*2], dist[N*2], vis[N*2], n, m;void addE(int i, int j, int ct, int cp){    cost[i][j]=ct;    cap[i][j]=cp;    cost[j][i]=-ct;    //cap[j][i]=0;}int s, t, minCost;void buildMap(){   int i, j;   memset(cap, 0, sizeof(cap));   s=0; t=cntM+cntH+1;   for(i=0; i
         

//邻接表

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define INF 0x3f3f3f3f#define N 1000005using namespace std;int cntH, cntM;struct node{    int x, y;};struct EDGE{    int u, v, cap, cost, nt;};EDGE edge[N];queue
         
          q;node man[105], house[105];int first[205];int dist[205];int pre[205], flow[205], vis[205];int cnt, t;int minCost;int n, m;void addEdge(int u, int v, int cap, int cost){ edge[cnt].u=u; edge[cnt].v=v; edge[cnt].cap=cap; edge[cnt].nt=first[u]; edge[cnt].cost=cost; first[u]=cnt++; edge[cnt].u=v; edge[cnt].v=u; edge[cnt].cap=0; edge[cnt].nt=first[v]; edge[cnt].cost=-cost; first[v]=cnt++;}void buildMap(){ memset(first, -1, sizeof(first)); t=cntH+cntM+1; for(int i=1; i<=cntM; ++i) for(int j=1; j<=cntH; ++j) addEdge(i, cntM+j, 1, abs(man[i].x-house[j].x) + abs(man[i].y-house[j].y)); for(int i=1; i<=cntM; ++i) addEdge(0, i, 1, 0); for(int i=1; i<=cntH; ++i) addEdge(cntM+i, t, 1, 0); }bool MCMF(){ memset(dist, 0x3f, sizeof(dist)); memset(vis, 0, sizeof(vis)); q.push(0); flow[0]=INF; dist[0]=0; vis[0]=1; while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int e=first[u]; ~e; e=edge[e].nt){ int v=edge[e].v, cap=edge[e].cap, cost=edge[e].cost; if(cap>0 && dist[v]>dist[u]+cost){ dist[v]=dist[u]+cost; flow[v]=min(flow[u], cap); pre[v]=e; if(!vis[v]){ vis[v]=1; q.push(v); } } } } if(dist[t]==INF) return false; minCost+=dist[t]; int x=t; while(x!=0){ edge[pre[x]].cap-=flow[t]; edge[pre[x]^1].cap+=flow[t]; x=edge[pre[x]].u; } return true;} int main(){ while(scanf("%d%d", &n, &m) && (n||m)){ cnt=cntH=cntM=0; for(int i=1; i<=n; ++i){ getchar(); for(int j=1; j<=m; ++j){ char ch; scanf("%c", &ch); if(ch=='m'){ man[++cntM].x=i; man[cntM].y=j; } else if(ch=='H'){ house[++cntH].x=i; house[cntH].y=j; } } } buildMap(); minCost=0; while(MCMF()); printf("%d\n", minCost); } return 0;}