hdu 3549 Flow Problem (Dinic)

 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 = 20;
14 
15 int N, M, my_map[my_max][my_max], my_source, my_sink
16     , my_dis[my_max];
17 
18 int my_dfs(int my_step, int my_ans)
19 {
20     if (my_step == my_sink) return my_ans;
21 
22     int my_temp = my_ans;
23     for (int i = 1; i <= N && my_ans; ++ i)
24     {
25         if (my_dis[my_step] == my_dis[i] + 1 && my_map[my_step][i])
26         {
27             int t = my_dfs(i, min(my_ans, my_map[my_step][i]));
28             my_map[my_step][i] -= t;
29             my_map[i][my_step] += t;
30             my_ans -= t;
31         }
32     }
33     return my_temp - my_ans;
34 }
35 
36 bool my_bfs()
37 {
38     memset(my_dis, -1, sizeof(my_dis));
39     queue <int> Q;
40     my_dis[my_sink] = 0;
41     Q.push(my_sink);
42     while (!Q.empty())
43     {
44         int now = Q.front();
45         for (int i = 1; i <= N; ++ i)
46         {
47             if (my_map[i][now] > 0 && my_dis[i] == -1)
48             {
49                 my_dis[i] = my_dis[now] + 1;
50                 Q.push(i);
51             }
52         }
53         if (now == my_source) return true;
54         Q.pop();
55     }
56     return false;
57 }
58 
59 int my_dinic()
60 {
61     int my_ans = 0;
62     while (my_bfs())
63         my_ans += my_dfs(my_source, INF);
64 
65     return my_ans;
66 }
67 
68 int main()
69 {
70     int t;
71     scanf("%d", &t);
72     for (int i = 1; i <= t; ++ i)
73     {
74         memset(my_map, 0, sizeof(my_map));
75         scanf("%d%d", &N, &M);
76         my_source = 1, my_sink = N;
77 
78         while (M --)
79         {
80             int x, y, x_y;
81             scanf("%d%d%d", &x, &y, &x_y);
82             my_map[x][y] += x_y;
83         }
84         printf("Case %d: %d\n", i, my_dinic());
85     }
86     return 0;
87 }