最小费用最大流 换模板。
#include <iostream> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <cmath> #include <vector> #include <queue> #include <algorithm> #include <map> using namespace std; const int maxn = 1010; const int INF = 0x3f3f3f3f; struct Edge { int from, to, cap, flow, cost; Edge(int from, int to, int cap, int flow, int cost): from(from), to(to), cap(cap), flow(flow), cost(cost) {} }; struct MCMF { int n, m, s, t; vector<Edge> edges; vector<int> G[maxn]; int inq[maxn]; int d[maxn]; int p[maxn]; int a[maxn]; void init(int n) { this->n = n; for(int i = 0; i <= n; i++) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap, int cost) { edges.push_back(Edge (from, to, cap, 0, cost)); edges.push_back(Edge (to, from, 0, 0, -cost)); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool spfa(int s, int t, int &flow, int &cost) { for(int i = 0; i <= n; i++) d[i] = INF; memset(inq, 0, sizeof(inq)); d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF; queue<int> Q; Q.push(s); while(!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = 0; for(int i = 0; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if(e.cap > e.flow && d[e.to] > d[u]+e.cost) { d[e.to] = d[u]+e.cost; p[e.to] = G[u][i]; a[e.to] = min(a[u], e.cap-e.flow); if(!inq[e.to]) { Q.push(e.to); inq[e.to] = 1; } } } } if(d[t] == INF) return 0; flow += a[t]; cost += d[t]*a[t]; int u = t; while(u != s) { edges[p[u]].flow += a[t]; edges[p[u]^1].flow -= a[t]; u = edges[p[u]].from; } return 1; } int Mincost(int s, int t, int &flow, int &cost) { while(spfa(s, t, flow, cost)); return cost; } }; void readint(int &x) { char c; while(!isdigit(c)) c = getchar(); x = 0; while(isdigit(c)) { x = x*10 + c-'0'; c = getchar(); } } void writeint(int x) { if(x > 9) writeint(x/10); putchar(x%10+'0'); } /////////////////////////////////////// MCMF solver; int n, m, s, t; struct Point { int x, y; Point(int x=0, int y=0): x(x), y(y) {} }; Point M[maxn], H[maxn]; int hh, mm; int Dist(Point a, Point b) { return abs(a.x-b.x)+abs(a.y-b.y); } char str[maxn][maxn]; void read_case() { hh = mm = 0; for(int i = 0; i < n; i++) scanf("%s", str[i]); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) { if(str[i][j] == 'm') { M[mm++] = Point(i, j); } else if(str[i][j] == 'H') H[hh++] = Point(i, j); } } void build() { s = hh+mm+1, t = hh+mm+2; solver.init(hh+mm+10); for(int i = 0; i < mm; i++) for(int j = 0; j < hh; j++) { int cost = Dist(M[i], H[j]); solver.AddEdge(i, j+mm, 1, cost); } for(int i = 0; i < mm; i++) solver.AddEdge(s, i, 1, 0); for(int i = 0; i < hh; i++) solver.AddEdge(i+mm, t, 1, 0); } void solve() { read_case(); build(); int cost = 0, flow = 0; int ans = solver.Mincost(s, t, flow, cost); printf("%d\n", cost); } int main() { while(~scanf("%d%d", &n, &m) && (n || m)) { solve(); } return 0; }