爱站程序员基地这个题目难点就是建图，其他啥也不是，套板子就完事了，体会一下这样建图就好了
#include<iostream>#include<stdio.h>#include<math.h>#include<string.h>#include<string>#include<vector>#include<queue>#include<algorithm>#include<deque>#include<map>#include<stdlib.h>#include<set>#include<iomanip>#include<stack>#define ll long long#define ms(a,b) memset(a,b,sizeof(a))#define lowbit(x) x & -x#define fi first#define se second#define bug cout<<\"----acac----\"<<endl#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)using namespace std;const int maxn = 1e4 + 50;const int maxm = 1.5e5+50;const double eps = 1e-7;const double inf = 0x3f3f3f3f;const ll lnf = 0x3f3f3f3f3f3f3f3f;const int mod = 1e9+7;const double pi=3.141592653589;int n,m,len=0;char p[105][105];int mp[105][2],hp[105][2],head[10050];struct node{int fa,to,next,c,cost;}a[maxn<<2];void add(int u,int v,int c,int cost){a[len].fa=u,a[len].c=c,a[len].cost=cost,a[len].to=v,a[len].next=head[u],head[u]=len++;a[len].fa=v,a[len].c=0,a[len].cost=-cost,a[len].to=u,a[len].next=head[v],head[v]=len++;}int dis[maxn],vis[maxn],pre[maxn];bool spfa(int s,int en){queue<int>q;for(int i=0;i<=en;i++){vis[i]=0;dis[i]=inf;pre[i]=-1;}dis[s]=0;q.push(s);vis[s]=1;while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=head[u];~i;i=a[i].next){if(a[i].c>0){int v=a[i].to;if(dis[v]>dis[u]+a[i].cost){dis[v]=dis[u]+a[i].cost;pre[v]=i;if(!vis[v]){vis[v]=1;q.push(v);}}}}}return dis[en]!=inf;}int f(int s,int en){int ans=0,flow;int flow_sum=0;while(spfa(s,en)){flow=inf;for(int i=pre[en];~i;i=pre[a[i].fa]){if(a[i].c<flow)flow=a[i].c;}for(int i=pre[en];~i;i=pre[a[i].fa]){a[i].c-=flow;a[i^1].c+=flow;}ans+=dis[en]*flow;// printf(\"%d\\n\",dis[en]*flow);flow_sum+=flow;}return ans;}int main(){while(~scanf(\"%d%d\",&n,&m)){if(n==0&&m==0)break;for(int i=1;i<=n;i++){scanf(\"%s\",p[i]+1);}int hcnt=0,mcnt=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(p[i][j]==\'H\'){hp[++hcnt][0]=i;hp[hcnt][1]=j;}else if(p[i][j]==\'m\'){mp[++mcnt][0]=i;mp[mcnt][1]=j;}}}ms(head,-1);len=0;// printf(\"%d %d\\n\",hcnt,mcnt);for(int i=1;i<=hcnt;i++){add(0,i,1,0);}for(int i=1;i<=mcnt;i++){add(hcnt+i,mcnt+hcnt+1,1,0);}for(int i=1;i<=hcnt;i++){for(int j=1;j<=mcnt;j++){add(i,hcnt+j,1,abs(mp[i][0]-hp[j][0])+abs(mp[i][1]-hp[j][1]));}}int ans=f(0,mcnt+hcnt+1);printf(\"%d\\n\",ans);}return 0;}
