HDU 1533 二分图最小权匹配 Going Home-白红宇

HDU 1533 二分图最小权匹配 Going Home

阅读量：5156 次

发布时间：2019-06-13

本文共 2164 字，大约阅读时间需要 7 分钟。

带权二分图匹配，把距离当做权值，因为是最小匹配，所以把距离的相反数当做权值求最大匹配。

最后再把答案取一下反即可。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
            6 #include 
           
             7 #include 
            
              8 #define MP make_pair 9 using namespace std; 10 11 typedef pair
             
               PII; 12 13 const int maxn = 100 + 10; 14 15 int n; 16 PII house[maxn], men[maxn]; 17 char grid[maxn][maxn]; 18 19 int row, col; 20 21 int dist(const PII& a, const PII& b) 22 { return abs(a.first - b.first) + abs(a.second - b.second); } 23 24 //KM algorithm 25 int W[maxn][maxn]; 26 int Lx[maxn], Ly[maxn]; 27 int lft[maxn]; 28 bool S[maxn], T[maxn]; 29 30 bool match(int u) 31 { 32 S[u] = true; 33 for(int v = 1; v <= n; v++) 34 if(Lx[u] + Ly[v] == W[u][v] && !T[v]) 35 { 36 T[v] = true; 37 if(!lft[v] || match(lft[v])) 38 { 39 lft[v] = u; 40 return true; 41 } 42 } 43 return false; 44 } 45 46 void update() 47 { 48 int a = 100000000; 49 for(int u = 1; u <= n; u++) if(S[u]) 50 for(int v = 1; v <= n; v++) if(!T[v]) 51 a = min(a, Lx[u] + Ly[v] - W[u][v]); 52 for(int u = 1; u <= n; u++) 53 { 54 if(S[u]) Lx[u] -= a; 55 if(T[u]) Ly[u] += a; 56 } 57 } 58 59 void KM() 60 { 61 for(int i = 1; i <= n; i++) 62 { 63 Lx[i] = *max_element(W[i]+1, W[i]+1+n); 64 Ly[i] = 0; 65 lft[i] = 0; 66 } 67 for(int u = 1; u <= n; u++) 68 { 69 for(;;) 70 { 71 memset(S, false, sizeof(S)); 72 memset(T, false, sizeof(T)); 73 if(match(u)) break; 74 else update(); 75 } 76 } 77 } 78 79 int main() 80 { 81 while(scanf("%d%d", &row, &col) == 2 && row) 82 { 83 n = 0; 84 85 for(int i = 0; i < row; i++) scanf("%s", grid[i]); 86 int hcnt = 0, mcnt = 0; 87 for(int i = 0; i < row; i++) 88 for(int j = 0; j < col; j++) 89 { 90 if(grid[i][j] == 'H') 91 house[++hcnt] = MP(i, j); 92 else if(grid[i][j] == 'm') 93 men[++mcnt] = MP(i, j); 94 } 95 96 //build graph 97 n = hcnt; 98 for(int i = 1; i <= n; i++) 99 for(int j = 1; j <= n; j++)100 W[i][j] = -dist(men[i], house[j]);101 102 KM();103 104 int ans = 0;105 for(int i = 1; i <= n; i++) ans += W[lft[i]][i];106 printf("%d\n", -ans);107 }108 109 return 0;110 }