kuangbin专题专题十一 网络流 Going Home POJ - 2195

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <queue>
  7 #include <cmath>
  8 using namespace std;
  9 
 10 const int N = 510,INF = (int)1e9;
 11 int n,m,tot,num;
 12 int head[N<<2],d[N<<2],vis[N<<2],pre[N<<2];
 13 char mp[N][N];
 14 vector<pair<int,int > > p;
 15 vector<pair<int,int > > h;
 16 struct node{
 17     int to,nxt,cap,flow,cost;
 18 }e[N*N];
 19 
 20 void show(){
 21     cout << endl;
 22     for(int i = 0; i < n; ++i) cout << mp[i] << endl;
 23     for(int i = 0; i < num; ++i) printf("( %d, %d) ",p[i].first,p[i].second);
 24     cout << endl;
 25     for(int i = 0; i < num; ++i) printf("( %d, %d) ",h[i].first,h[i].second);
 26     cout << endl << endl;
 27 }
 28 //求距离
 29 inline int _dis(int x,int y){
 30     return abs(p[x].first - h[y].first) + abs(p[x].second - h[y].second);
 31 }
 32 
 33 inline void add(int u,int v,int cap,int flow,int cost){
 34     e[tot].to = v;
 35     e[tot].cap = cap;
 36     e[tot].flow = flow;
 37     e[tot].cost = cost;
 38     e[tot].nxt = head[u];
 39     head[u] = tot++;
 40     e[tot].to = u;
 41     e[tot].cap = 0;
 42     e[tot].flow = flow;
 43     e[tot].cost = -cost;
 44     e[tot].nxt = head[v];
 45     head[v] = tot++;
 46 }
 47 
 48 void build_map(int s,int t){
 49     
 50     //0源点 1~num人  num+1~2*num 房入 2*num+1~3*num房出 3*num+1汇点
 51     int cost;
 52     for(int i = 0; i < num; ++i){
 53         for(int j = 0; j < num; ++j){
 54             cost = _dis(i,j);
 55             add(i+1,j+1+num,1,0,cost);
 56         }
 57     }
 58     for(int i = 0; i < num; ++i) add(s,i+1,1,0,0);
 59     for(int i = 0; i < num; ++i) add(i+1+num,i+1+2*num,1,0,0);
 60     for(int i = 0; i < num; ++i) add(i+1+2*num,t,1,0,0);
 61 }
 62 
 63 bool spfa(int s,int t){
 64     for(int i = s; i <= t; ++i) pre[i] = -1;
 65     for(int i = s; i <= t; ++i) d[i] = INF; d[s] = 0;
 66     for(int i = s; i <= t; ++i) vis[i] = false; vis[s] = true;
 67     queue<int > que;
 68     que.push(s);
 69     while(!que.empty()){
 70         int now = que.front(); que.pop();
 71         vis[now] = false;
 72         for(int o = head[now]; ~o; o = e[o].nxt){
 73             int to = e[o].to;
 74             if(e[o].cap > e[o].flow && d[to] > d[now] + e[o].cost){
 75                 d[to] = d[now] + e[o].cost;
 76                 pre[to] = o;
 77                 if(!vis[to])
 78                     vis[to] = true;
 79                     que.push(to);
 80             }
 81         }
 82     }
 83     if(pre[t] == -1) return false;
 84     else return true;
 85 }
 86 
 87 int work(){
 88 
 89     int s = 0,t = 3*num+1,ans = 0;
 90     for(int i = s; i <= t; ++i) head[i] = -1; tot = 0;
 91     build_map(s,t);
 92     while(spfa(s,t)){
 93         int Min = INF;
 94         for(int o = pre[t]; ~o; o = pre[e[o^1].to]){
 95             Min = min(Min,e[o].cap - e[o].flow);
 96         }
 97         for(int o = pre[t]; ~o; o = pre[e[o^1].to]){
 98             e[o].flow += Min;
 99             e[o^1].flow -= Min;
100         }
101         ans += Min*d[t];
102     }
103     return ans;
104 }
105 
106 int main(){
107 
108     while(~scanf("%d%d",&n,&m) && (n+m)){
109         for(int i = 0; i < n; ++i) scanf("%s",mp[i]);
110         p.clear(); h.clear();
111         for(int i = 0; i < n; ++i){
112             for(int j = 0; j < m; ++j){
113                 if(mp[i][j] == 'm') p.push_back(make_pair(i,j));
114                 if(mp[i][j] == 'H') h.push_back(make_pair(i,j));
115             }
116         }
117         num = p.size();
118         //show();
119         //cout <<  "------------------------------------" << work() << endl;
120         cout << work() << endl;
121     }
122 
123     return 0;
124 }