这就是一道最小费用最大流问题
最大流就体现到每一个‘m’都能找到一个‘H’，但是要在这个基础上面加一个费用，按照题意费用就是（横坐标之差的绝对值加上纵坐标之差的绝对值）
然后最小费用最大流模板就是再用最短路算法找最小费用路径。然后在找到这条路径上面的最大流。。就这样一直找下去
代码：
1 //这是一个最小费用最大流问题 2 //最大费用最小流只要在添加边的时候换一下位置就好了 3 //求最大费用最大流只需要把费用换成相反数，用最小费用最大流求解即可 4 #include <cstdio> 5 #include <cstring> 6 #include <algorithm> 7 #include <queue> 8 #include <cmath> 9 using namespace std; 10 const int MAXN = 10000; 11 const int MAXM = 100000; 12 const int INF = 0x3f3f3f3f; 13 struct Edge 14 { 15 int v, next, cap, flow, cost; 16 int x, y; 17 } e[MAXM]; 18 struct shudui 19 { 20 int x,y; 21 }p1[MAXN],p2[MAXN]; 22 int head[MAXN],tol; 23 int pre[MAXN],dis[MAXN]; 24 bool vis[MAXN]; 25 int N, M; 26 void init() 27 { 28 N = MAXN; 29 tol = 0; 30 memset(head, -1, sizeof(head)); 31 } 32 void add_edge(int x,int y,int cap,int cost) 33 { 34 e[tol].v=y; 35 e[tol].cap=cap; 36 e[tol].flow=0; 37 e[tol].cost=cost; 38 e[tol].next=head[x]; 39 head[x]=tol++; 40 41 e[tol].v=x; 42 e[tol].cap=0; 43 e[tol].flow=0; 44 e[tol].cost=-cost; 45 e[tol].next=head[y]; 46 head[y]=tol++; 47 } 48 int spfa(int s,int t) 49 { 50 queue<int>r; 51 for(int i=0;i<MAXN;++i) 52 { 53 vis[i]=0; 54 dis[i]=INF; 55 pre[i]=-1; 56 } 57 dis[s]=0; 58 vis[s]=1; 59 r.push(s); 60 while(!r.empty()) 61 { 62 //printf("**\n"); 63 int u=r.front(); 64 r.pop(); 65 vis[u]=0; 66 for(int i=head[u];i!=-1;i=e[i].next) 67 { 68 int v=e[i].v; 69 if(e[i].cap>e[i].flow && dis[v]>dis[u]+e[i].cost) 70 { 71 dis[v]=dis[u]+e[i].cost; 72 pre[v]=i; 73 if(!vis[v]) 74 { 75 vis[v]=1; 76 r.push(v); 77 } 78 } 79 } 80 } 81 if(pre[t]==-1) return 0; 82 else return 1; 83 } 84 int MincostMaxflow(int s,int t,int &cost) 85 { 86 int flow=0; 87 cost=0; 88 while(spfa(s,t)) 89 { 90 91 int minn=INF; 92 for(int i=pre[t];i!=-1;i=pre[e[i^1].v]) 93 { 94 if(minn>e[i].cap-e[i].flow) 95 { 96 minn=e[i].cap-e[i].flow; 97 } 98 } 99 for(int i=pre[t];i!=-1;i=pre[e[i^1].v]) 100 { 101 e[i].flow+=minn; 102 e[i^1].flow-=minn; 103 cost+=e[i].cost*minn; 104 } 105 flow+=minn; 106 } 107 return flow; 108 } 109 110 int main() 111 { 112 int n,m,st,en; 113 char s[105][105]; 114 while(~scanf("%d%d",&n,&m) && n+m) 115 { 116 init(); 117 int index1=0,index2=0; 118 for(int i=1;i<=n;++i) 119 scanf("%s",s[i]+1); 120 st=0; 121 for(int i=1;i<=n;++i) 122 { 123 for(int j=1;j<=m;++j) 124 { 125 if(s[i][j]=='m') 126 { 127 index1++; 128 p1[index1].x=i; 129 p1[index1].y=j; 130 131 } 132 else if(s[i][j]=='H') 133 { 134 index2++; 135 p2[index2].x=i; 136 p2[index2].y=j; 137 138 } 139 } 140 } 141 //printf("%d %d\n",index1,index2); 142 en=index1+index2+1; 143 for(int i=1;i<=index1;++i) 144 { 145 add_edge(st,i,1,0); 146 } 147 for(int i=index1+1;i<=index1+index2;++i) 148 { 149 add_edge(i,en,1,0); 150 } 151 for(int i=1;i<=index1;++i) 152 { 153 for(int j=1;j<=index2;++j) 154 { 155 int cost=abs(p1[i].x-p2[j].x)+abs(p1[i].y-p2[j].y); 156 add_edge(i,index1+j,1,cost); 157 } 158 } 159 int ans=0; 160 MincostMaxflow(st,en,ans); 161 printf("%d\n",ans); 162 } 163 return 0; 164 }