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
34void dfs(int u) {
35 //cout << u << " ";
36 for(auto item: adj[u]) {
37 int v = item.first;
38 int w = item.second;
39 // Neu dinh v chua duoc tham
40 if(parent[v] == -1 && RC[u][v]) {
41 parent[v] = u; // Ghi nhan cha cua v la u
42 add_flow = min(add_flow, RC[u][v]);
43 dfs(v);
44 }
45 }
46}
47
48// Giai thuat Ford_Fulkerson
49// s: dinh bat dau
50// t: dinh ket thuc
51// n: so luong dinh
52int maxFlow_Ford_Fulkerson(int s, int t, int n) {
53 int flow = 0;
54 while(1) {
55 // Khoi tao
56 memset(parent, NULL_INT, sizeof(parent));
57 parent[s] = 0;
58 add_flow = INT_MAX;
59
60 dfs(s);
61 if(parent[t] == NULL_INT) {
62 break;
63 }
64 flow += add_flow;
65 int v = t;
66 while(v != s) {
67 int u = parent[v];
68 RC[v][u] += add_flow; // cung nguoc
69 RC[u][v] -= add_flow; // cung xuoi
70 v = u;
71 }
72 }
73 return flow;
74}
75
76int main() {
77 // Chuyen NHAP, XUAT thanh file
78 freopen("lab_8_input.INP", "r", stdin);
79 freopen("lab_8_output.OUT", "w", stdout);
80
81 // INPUT
82 inp();
83
84 // OUTPUT
85 int s = 1;
86 int t = n;
87 cout << maxFlow_Ford_Fulkerson(s, t, n);
88 return 0;
89}