1 #include<iostream>
 2 #include<queue>
 3 #include<cstdio>
 4 #include<cstring>
 5 using namespace std;
 6 int res[20][20], vis[20], pre[20];
 7 queue<int>q;
 8 int N, M;
 9 bool bds(int s, int t)
10 {
11     memset(vis, 0, sizeof(vis));
12     memset(pre, -1, sizeof(pre));
13     while(!q.empty())
14         q.pop();
15     q.push(s);
16     vis[s] = 1;
17     while(!q.empty())
18     {
19         int p = q.front();
20         q.pop();
21         for(int i = 1;i <= N;i ++)
22         {
23             if(!vis[i] && res[p][i] > 0)
24             {
25                 vis[i] = 1;
26                 pre[i] = p;
27                 q.push(i);
28                 if(i == t)
29                     return true;
30             }
31         }
32     }
33     return false;
34 }
35 
36 int EK(int s, int t)
37 {
38     int flow = 0, d, i, u;
39     while(bds(s, t))
40     {
41         d = 1 << 30;
42         u = t;
43         while(pre[u] != -1)
44         {
45             d = min(d, res[pre[u]][u]);
46             u = pre[u];
47         }
48         u = t;
49         while(pre[u] != -1)
50         {
51             res[pre[u]][u] -= d;
52             res[u][pre[u]] += d;
53             u = pre[u];
54         }
55         flow += d;
56     }
57     return flow;
58 }
59 
60 int main(int argc, char const *argv[]) 
61 {
62     int T, u, v, w, cnt = 0;
63     //freopen("in.c", "r", stdin);
64     scanf("%d", &T);
65     while(T--)
66     {
67         memset(res, 0, sizeof(res));
68         scanf("%d%d", &N, &M);
69         for(int i = 0;i < M;i ++)
70         {
71             scanf("%d%d%d", &u, &v, &w);
72             res[u][v] += w;
73         }
74         printf("Case %d: %d\n", ++cnt, EK(1, N));
75     }
76     return 0;
77 }

 1 #include<iostream>
 2 #include<queue>
 3 #include<cstring>
 4 #include<cstdio>
 5 using namespace std;
 6 int res[20][20], level[20], N, M, flow;
 7 queue<int>q;
 8 bool bfs(int s)
 9 {
10     while(!q.empty())
11         q.pop();
12     memset(level, -1, sizeof(level));
13     level[s] = 0;
14     q.push(s);
15     while(!q.empty())
16     {
17         int p = q.front();
18         q.pop();
19         for(int i = 1;i <= N;i ++)
20         {
21             if(level[i] == -1 && res[p][i] > 0)
22             {
23                 level[i] = level[p] + 1;
24                 q.push(i);
25             }
26         }
27     }
28     if(level[N] >= 0)
29         return true;
30     return false;
31 }
32 
33 int dinic(int s, int sum)
34 {
35     if(s == N)
36         return sum;
37     int os = sum;
38     for(int i = 1;i <= N;i ++)
39     {
40         if(level[i] == level[s] + 1 && res[s][i] > 0)
41         {
42             int temp = dinic(i, min(sum, res[s][i]));
43             res[s][i] -= temp;
44             res[i][s] += temp;
45             sum -= temp;
46         }
47     }
48     return os - sum;
49 }
50 
51 int main(int argc, char const *argv[]) 
52 {
53     int T, u, v, w,cnt = 0;
54    // freopen("in.c", "r", stdin);
55     scanf("%d", &T);
56     while(T--)
57     {
58         flow = 0;
59         memset(res, 0, sizeof(res));
60         scanf("%d%d", &N, &M);
61         for(int i = 0; i < M;i ++)
62         {
63             scanf("%d%d%d", &u, &v, &w);
64             res[u][v] += w;
65         }
66         while(bfs(1))
67             flow += dinic(1,1 << 30);
68         printf("Case %d: %d\n", ++cnt,flow);
69     }
70     return 0;
71 }