题意：http://acm.hdu.edu.cn/showproblem.php?pid=1533
相邻的容量为inf，费用为1，S到m容量为1，费用为0 ，H到T容量为1，费用为0。
建图跑-最小费用最大流-就行了。
1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0); 2 #include <cstdio>//sprintf islower isupper 3 #include <cstdlib>//malloc exit strcat itoa system("cls") 4 #include <iostream>//pair 5 #include <fstream>//freopen("C:\\Users\\13606\\Desktop\\Input.txt","r",stdin); 6 #include <bitset> 7 //#include <map> 8 //#include<unordered_map> 9 #include <vector> 10 #include <stack> 11 #include <set> 12 #include <string.h>//strstr substr 13 #include <string> 14 #include <time.h>// srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9; 15 #include <cmath> 16 #include <deque> 17 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less 18 #include <vector>//emplace_back 19 //#include <math.h> 20 #include <cassert> 21 //#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor 22 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare) 23 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation 24 //****************** 25 int abss(int a); 26 int lowbit(int n); 27 int Del_bit_1(int n); 28 int maxx(int a,int b); 29 int minn(int a,int b); 30 double fabss(double a); 31 void swapp(int &a,int &b); 32 clock_t __STRAT,__END; 33 double __TOTALTIME; 34 void _MS(){__STRAT=clock();} 35 void _ME(){__END=clock();__TOTALTIME=(double)(__END-__STRAT)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;} 36 //*********************** 37 #define rint register int 38 #define fo(a,b,c) for(rint a=b;a<=c;++a) 39 #define fr(a,b,c) for(rint a=b;a>=c;--a) 40 #define mem(a,b) memset(a,b,sizeof(a)) 41 #define pr printf 42 #define sc scanf 43 #define ls rt<<1 44 #define rs rt<<1|1 45 typedef pair<int,int> PII; 46 typedef vector<int> VI; 47 typedef long long ll; 48 const double E=2.718281828; 49 const double PI=acos(-1.0); 50 //const ll INF=(1LL<<60); 51 const int inf=(1<<30); 52 const double ESP=1e-9; 53 const int mod=(int)1e9+7; 54 const int N=(int)1e5+10; 55 56 int n,m,S,T; 57 class MCMF 58 { 59 public: 60 struct node 61 { 62 int u,v,f,w,nxt; 63 }edge[N]; 64 int head[N],tot; 65 int h[N],dis[N],PrePoint[N],PreEdge[N]; 66 void Init(int n) 67 { 68 tot=-1; 69 for(int i=0;i<=n;++i) 70 head[i]=-1,h[i]=0; 71 } 72 void add(int x,int y,int f,int w) 73 { 74 ++tot; 75 edge[tot]={x,y,f,w,head[x]}; 76 head[x]=tot; 77 } 78 void Add(int x,int y,int f,int w) 79 { 80 add(x,y,f,w); 81 add(y,x,0,-w); 82 } 83 PII Dij() 84 { 85 int max_flow=0,min_cost=0; 86 while(1) 87 { 88 priority_queue<PII>q; 89 for(int i=1;i<=n;++i) 90 dis[i]=inf; 91 dis[S]=0; 92 q.push({0,S}); 93 while(!q.empty()) 94 { 95 PII now=q.top();q.pop(); 96 if(-now.first!=dis[now.second])continue; 97 if(now.second==T)break; 98 for(int i=head[now.second];i!=-1;i=edge[i].nxt) 99 { 100 int nowcost=edge[i].w+h[now.second]-h[edge[i].v]; 101 if(edge[i].f>0&&dis[edge[i].v]>dis[now.second]+nowcost) 102 { 103 dis[edge[i].v]=dis[now.second]+nowcost; 104 q.push({-dis[edge[i].v],edge[i].v}); 105 PrePoint[edge[i].v]=now.second; 106 PreEdge[edge[i].v]=i; 107 } 108 } 109 } 110 if(dis[T]==inf)break; 111 for(int i=0;i<=n;++i)h[i]+=dis[i]; 112 int nowflow=inf; 113 for(int i=T;i!=S;i=PrePoint[i]) 114 nowflow=min(nowflow,edge[PreEdge[i]].f); 115 for(int i=T;i!=S;i=PrePoint[i]) 116 { 117 edge[PreEdge[i]].f-=nowflow; 118 edge[PreEdge[i]^1].f+=nowflow; 119 } 120 max_flow+=nowflow; 121 min_cost+=nowflow*h[T]; 122 } 123 return {max_flow,min_cost}; 124 } 125 }G; 126 127 char mp[103][103]; 128 int id[103][103]; 129 130 int main() 131 { 132 int h,l; 133 while(sc("%d%d",&h,&l),h&&l) 134 { 135 S=h*l+1,T=h*l+2; 136 int cnt=0; 137 fo(i,1,h) 138 fo(j,1,l) 139 sc("%1s",&mp[i][j]),id[i][j]=++cnt; 140 n=h*l+2; 141 G.Init(n); 142 for(int i=1;i<=h;++i) 143 { 144 for(int j=1;j<=l;++j) 145 { 146 if(i>1)G.Add(id[i][j],id[i-1][j],inf,1); 147 if(j>1)G.Add(id[i][j],id[i][j-1],inf,1); 148 if(i<h)G.Add(id[i][j],id[i+1][j],inf,1); 149 if(j<l)G.Add(id[i][j],id[i][j+1],inf,1); 150 if(mp[i][j]=='m')G.Add(S,id[i][j],1,0); 151 if(mp[i][j]=='H')G.Add(id[i][j],T,1,0); 152 } 153 } 154 PII ans=G.Dij(); 155 pr("%d\n",ans.second); 156 } 157 return 0; 158 } 159 160 /**************************************************************************************/ 161 162 int maxx(int a,int b) 163 { 164 return a>b?a:b; 165 } 166 167 void swapp(int &a,int &b) 168 { 169 a^=b^=a^=b; 170 } 171 172 int lowbit(int n) 173 { 174 return n&(-n); 175 } 176 177 int Del_bit_1(int n) 178 { 179 return n&(n-1); 180 } 181 182 int abss(int a) 183 { 184 return a>0?a:-a; 185 } 186 187 double fabss(double a) 188 { 189 return a>0?a:-a; 190 } 191 192 int minn(int a,int b) 193 { 194 return a<b?a:b; 195 }