Going Home HDU - 1533 (费用流）

  1 //费用流初探
  2 #include <iostream>
  3 #include <queue>
  4 #include <cstring>
  5 #include <cstdio>
  6 #include <algorithm>
  7 using namespace std;
  8 const int inf = 0x3f3f3f3f;
  9 const int maxn = 110;
 10 char gra[maxn][maxn];
 11 
 12 const int maxv =  210;
 13 const int maxe = 210 * 210;
 14 struct Edge{
 15     int u, v, cap, flow, cost;
 16     int nxt;
 17     Edge(int u = 0, int v = 0, int cap = 0, int flow = 0, int cost = 0, int nxt = 0) : u(u), v(v), cap(cap), flow(flow), cost(cost), nxt(nxt) {}
 18 }e[maxe << 1];
 19 int head[maxv];
 20 int cnt = 0;
 21 void init(){
 22     memset(head, -1, sizeof(head));
 23     cnt = 0;
 24 }
 25 void add(int u, int v, int cap, int flow, int cost){
 26     e[cnt] = Edge(u, v, cap, flow, cost, head[u]);
 27     head[u] = cnt++;
 28     e[cnt] = Edge(v, u, 0, flow, -cost, head[v]);
 29     head[v] = cnt++;
 30 }
 31 int mx[maxv], my[maxv], hx[maxv], hy[maxv];
 32 
 33 int s, t, N;
 34 int d[maxv], p[maxv], inq[maxv], a[maxv];
 35 bool BellmandFord(int s, int t, int &flow, int &cost){
 36     for(int i = 0; i < N; i++) d[i] = inf;
 37     memset(inq, 0, sizeof inq);
 38     d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = inf;
 39     queue<int> q;
 40     q.push(s);
 41     while(!q.empty()){
 42         int u = q.front(); q.pop();
 43         inq[u] = 0;
 44         for(int i = head[u]; ~i; i = e[i].nxt){
 45             Edge &tp = e[i];
 46             if(tp.cap > tp.flow && d[tp.v] > d[u] + tp.cost){
 47                 d[tp.v] = d[u] + tp.cost;
 48                 p[tp.v] = i;
 49                 a[tp.v] = min(a[u], tp.cap - tp.flow);
 50                 if(!inq[tp.v]) {
 51                     q.push(tp.v);
 52                     inq[tp.v] = 1;
 53                 }
 54             }
 55         }
 56     }
 57     if(d[t] == inf) return false;
 58     flow += a[t];
 59     cost += d[t] * a[t];
 60     int u = t;
 61     while(u != s){
 62         e[p[u]].flow += a[t];
 63         e[p[u] ^ 1].flow -= a[t];
 64         u = e[p[u]].u;
 65     }
 66     return true;
 67 }
 68 int MCMF(){
 69     int flow = 0, cost = 0;
 70     while(BellmandFord(s, t, flow, cost)) ;
 71     return cost;
 72 }
 73 
 74 int main(){
 75     //freopen("in.txt", "r", stdin);
 76     //freopen("out.txt", "w", stdout);
 77     int n, m;
 78     while(scanf("%d %d", &n, &m) && (n || m)){
 79         int cth = 0, ctm = 0;
 80 
 81         init();
 82         for(int i = 0; i < n; i++) {
 83             scanf("%s", gra[i]);
 84             for(int j = 0; j < m; j++){
 85                 if(gra[i][j] == ‘H‘){
 86                     hx[cth] = i;
 87                     hy[cth++] = j;
 88                 }
 89                 if(gra[i][j] == ‘m‘){
 90                     mx[ctm] = i;
 91                     my[ctm++] = j;
 92                 }
 93             }
 94         }
 95         for(int i = 0; i < cth; i++){
 96             for(int j = 0; j < ctm; j++){
 97                 int dis = abs(hx[i] - mx[j]) + abs(hy[i] - my[j]);
 98                 add(i, cth + j, 1, 0, dis);
 99             }
100         }
101         s = cth + ctm;
102         t = s + 1;
103         N = t + 1;
104         for(int i = 0; i < cth; i++){
105             add(s, i, 1, 0, 0);
106         }
107         for(int i = 0; i < ctm; i++){
108             add(cth + i, t, 1, 0, 0);
109         }
110         int ans = MCMF();
111         printf("%d\n", ans);
112     }
113     return 0;
114 }