hdu 1533 Going Home (Dinic, 1)

  1 #include <map>
  2 #include <queue>
  3 #include <cmath>
  4 #include <vector>
  5 #include <string>
  6 #include <cstdio>
  7 #include <cstring>
  8 #include <climits>
  9 #include <iostream>
 10 #include <algorithm>
 11 #define INF 0x3f3f3f3f
 12 using namespace std;
 13 const int my_max = 110, my_max_hm = 5010;
 14 
 15 int my_map[my_max][my_max], n, m, N, my_line[my_max_hm]
 16     , my_lx[my_max_hm], my_ly[my_max_hm], my_slack[my_max_hm]
 17     , my_bookx[my_max_hm], my_booky[my_max_hm];
 18 
 19 struct node
 20 {
 21     int x, y;
 22 } my_home[my_max_hm], my_men[my_max_hm];
 23 
 24 bool my_dfs(int x)
 25 {
 26     my_bookx[x] = 1;
 27     for (int i = 1; i <= N; ++ i)
 28     {
 29         if (my_booky[i]) continue;
 30         int temp = my_lx[x] + my_ly[i] - my_map[x][i];
 31         if (temp == 0)
 32         {
 33             my_booky[i] = 1;
 34             if (!my_line[i] || my_dfs(my_line[i]))
 35             {
 36                 my_line[i] = x;
 37                 return true;
 38             }
 39         }
 40         else if (my_slack[i] > temp)
 41             my_slack[i] = temp;
 42     }
 43     return false;
 44 }
 45 
 46 int my_km()
 47 {
 48     memset(my_line, 0, sizeof(my_line));
 49     memset(my_ly, 0, sizeof(my_ly));
 50     for (int i = 1; i <= N; ++ i)
 51     {
 52         my_lx[i] = -INF;
 53         for (int j = 1; j <= N; ++ j)
 54             if (my_lx[i] < my_map[i][j])
 55                 my_lx[i] = my_map[i][j];
 56     }
 57 
 58     for (int i = 1; i <= N; ++ i)
 59     {
 60         for (int j = 1; j <= N; ++ j)
 61             my_slack[j] = INF;
 62         while (1)
 63         {
 64             memset(my_bookx, 0, sizeof(my_bookx));
 65             memset(my_booky, 0, sizeof(my_booky));
 66 
 67             if (my_dfs(i)) break;
 68             int my_temp_min = INF;
 69             for (int j = 1; j <= N; ++ j)
 70                 if (!my_booky[j] && my_slack[j] < my_temp_min)
 71                     my_temp_min = my_slack[j];
 72 
 73             for (int j = 1; j <= N; ++ j)
 74                 if (my_bookx[j]) my_lx[j] -= my_temp_min;
 75             for (int j = 1; j <= N; ++ j)
 76                 if (my_booky[j]) my_ly[j] += my_temp_min;
 77                 else my_slack[j] -= my_temp_min;
 78         }
 79     }
 80     int my_ans = 0;
 81     for (int i = 1; i <= N; ++ i)
 82         my_ans += my_map[my_line[i]][i];
 83     return my_ans;
 84 }
 85 
 86 int main()
 87 {
 88     while (scanf("%d%d", &n, &m), n || m)
 89     {
 90         int my_cnt_h = 0, my_cnt_m = 0;
 91         memset(my_map, 0, sizeof(my_map));
 92         getchar();
 93         for (int i = 1; i <= n; ++ i)
 94         {
 95             char my_s[my_max];
 96             scanf("%s", my_s);
 97             for (int j = 0; j < m; ++ j)
 98             {
 99                 if (my_s[j] == ‘H‘)
100                 {
101                     my_home[my_cnt_h].x = i;
102                     my_home[my_cnt_h].y = j;
103                     my_cnt_h ++;
104                 }
105                 else if (my_s[j] == ‘m‘)
106                 {
107                     my_men[my_cnt_m].x = i;
108                     my_men[my_cnt_m].y = j;
109                     my_cnt_m ++;
110                 }
111             }
112         }
113 
114         N = my_cnt_h;
115         for (int i = 1; i <= N; ++ i)
116         {
117             for (int j = 1; j <= N; ++ j)
118             {
119                 my_map[i][j] += abs(my_men[i - 1].x - my_home[j - 1].x);
120                 my_map[i][j] += abs(my_men[i - 1].y - my_home[j - 1].y);
121                 my_map[i][j] *= -1;
122             }
123         }
124         printf("%d\n", -1 * my_km());
125     }
126     return 0;
127 }