1#include<bits/stdc++.h>
2#include<iostream>
3using namespace std;
4using ll = long long;
5
6const int maxN = 1001;
7const int INF = 1e9; // so vo cung
8const int NULL_INT = -1;
9
10int n, m; // n: so dinh, m: so canh
11int s, t; // s: dinh bat dau, t: dinh ket thuc
12vector<pair<int, int>> adj[maxN];
13
14int parent[maxN];
15int RC[maxN][maxN]; // luu tru cung xuoi, cung nguoc
16int add_flow; // luu tru gia tri luong cuc dai
17
18
19void inp() {
20 cin >> n >> m;
21 for(int i = 0; i < m; i++) {
22 int x, y, z;
23 cin >> x >> y >> z;
24 adj[x].push_back({y, z});
25
26 // Do thi co huong thi comment dong code sau
27 adj[y].push_back({x, z});
28
29 // Luu tru gia tri trong so
30 RC[x][y] = z;
31 }
32}
33
34bool bfs(int s, int t, int n) {
35 // Khoi tao
36 memset(parent, NULL_INT, sizeof(parent));
37 parent[s] = 0;
38 add_flow = INT_MAX;
39
40 queue<int> q;
41 q.push(s);
42
43 // Lap
44 while(!q.empty()) {
45 int u = q.front(); // Lay phan tu o dau hang doi
46 q.pop(); // xoa bo phan tu o dau ra khoi hang doi
47 //cout << v << " ";
48 for(auto item: adj[u]) {
49 int v = item.first; // dinh v
50 int w = item.second; // trong so
51 if(parent[v] == NULL_INT && RC[u][v]) {
52 parent[v] = u; // Ghi nhan cha cua v la u
53 add_flow = min(add_flow, RC[u][v]);
54
55 if(v == t) { // neu lap den dinh ket thuc thi dung vong lap
56 return true;
57 }
58
59 q.push(v);
60 }
61 }
62 }
63 return false;
64}
65
66// Giai thuat Edmonds_Karp
67// s: dinh bat dau
68// t: dinh ket thuc
69// n: so luong dinh
70int maxFlow_Edmonds_Karp(int s, int t, int n) {
71 int flow = 0;
72 while(bfs(s, t, n)) {
73 flow += add_flow;
74 int v = t;
75 while(v != s) {
76 int u = parent[v];
77 RC[v][u] += add_flow; // cung nguoc
78 RC[u][v] -= add_flow; // cung xuoi
79 v = u;
80 }
81 }
82 return flow;
83}
84
85int main() {
86 // Chuyen NHAP, XUAT thanh file
87 freopen("lab_8_1_input.INP", "r", stdin);
88 freopen("lab_8_1_output.OUT", "w", stdout);
89
90 // INPUT
91 inp();
92
93 // OUTPUT
94 int s = 1;
95 int t = n;
96 cout << maxFlow_Edmonds_Karp(s, t, n);
97 return 0;
98}