POJ2195Going Home【KM】

题意：

给一个矩阵，m代表人H代表房子，现在想让人移动最少的步数回到房子中

分析：

可用二分图和网络流来写

二分图：X集合为人Y集合为房子，人与每个房子的连一条边为-dist的边即可，求出最大权值，然后取反即可

网络流：用费用流来做，人与房子之间建立容量为1，费用为dist的边，求出最小费用即可

由于人与每个房子之间有有边，所以我用的邻接矩阵处理的

二分图代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <map>
  5 #include <vector>
  6 #include <cmath>
  7 using namespace std;
  8 
  9 const int maxn = 105;
 10 const int INF = 1000000000;
 11 
 12 typedef pair<int, int> PII;
 13 vector<PII> v[2];
 14 
 15 
 16 int n_cnt;
 17 int W[maxn][maxn];
 18 int Lx[maxn], Ly[maxn];
 19 int Left[maxn];
 20 bool S[maxn], T[maxn];
 21 
 22 bool match(int i) {
 23     S[i] = true;
 24     for(int j = 1; j <= n_cnt; j++) if(Lx[i] + Ly[j] == W[i][j] && !T[j]) {
 25         T[j] = true;
 26         if(!Left[j] || match(Left[j])) {
 27             Left[j] = i;
 28             return true;
 29         }
 30     }
 31     return false;
 32 }
 33 
 34 
 35 void update() {
 36     int a = INF;
 37     for(int i = 1; i <= n_cnt; i++) if(S[i]) {
 38         for(int j = 1; j <= n_cnt; j++) if(!T[j]) {
 39             a = min(a, Lx[i] + Ly[j] - W[i][j]);
 40         }
 41     }
 42     for(int i = 1; i <= n_cnt; i++) {
 43         if(S[i]) Lx[i] -= a;
 44         if(T[i]) Ly[i] += a;
 45     }
 46 }
 47 
 48 void KM() {
 49     for(int i = 1; i <= n_cnt; i++) {
 50         Left[i] = Lx[i] = Ly[i] = 0;
 51         for(int j = 1; j <= n_cnt; j++) {
 52             Lx[i] = max(Lx[i], W[i][j]);
 53         }
 54     }
 55     for(int i = 1; i <= n_cnt; i++) {
 56         for(;;) {
 57             for(int j = 1; j <= n_cnt; j++) S[j] = T[j] = 0;
 58             if(match(i)) break;
 59             else update();
 60         }
 61     }
 62 }
 63 
 64 int dist(PII p1, PII p2) {
 65     return fabs(p1.first - p2.first) + fabs(p1.second - p2.second);
 66 }
 67 
 68 int main() {
 69     int n, m;
 70 //    freopen("a.txt","r",stdin);
 71     while(scanf("%d %d",&n, &m) && n + m) {
 72         char mat[maxn][maxn];
 73         memset(W, 0, sizeof(W));
 74         v[0].clear(); v[1].clear();
 75         for(int i = 0; i < n; i++) {
 76                 scanf("
%s",mat[i]);
 77                // puts(mat[i]);
 78         }
 79         for(int i = 0; i < n; i++) {
 80             for(int j = 0; j < m; j++) {
 81                 if(mat[i][j] == 'm')
 82                     v[0].push_back(make_pair(i, j));
 83                 else if(mat[i][j] == 'H')
 84                     v[1].push_back(make_pair(i, j));
 85             }
 86         }
 87         n_cnt = v[0].size();
 88 //        printf("n == %d
",n_cnt);
 89         for(int i = 0; i < n_cnt; i++) {
 90             for(int j = 0; j < n_cnt; j++) {
 91                 W[i + 1][j + 1] = -dist(v[0][i], v[1][j]);
 92             }
 93         }
 94         KM();
 95         int ans = 0;
 96         for(int i = 1; i <= n_cnt; i++) {
 97             ans += Lx[i] + Ly[i];
 98         }
 99         printf("%d
",-ans);
100     }
101     return 0;
102 }

View Code