首页 > 代码库 > POJ2195Going Home【KM】

POJ2195Going Home【KM】

2024-07-16 04:56:35   220人阅读

题意：

给一个矩阵，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("\n%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",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\n",-ans);100     }101     return 0;102 }
View Code






























        

            
                
                  
                
                

                    联系

                    我们