1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#include <cctype>
#include <algorithm>
#define rg register
const int maxn = 1e5 + 7;
const int inf = 2147483647;
using namespace std;
namespace _lgl{
int n, m, s, t, tot, head[maxn];
bool vis[maxn];
struct edge{
int to, val, next;
}e[maxn << 1];
struct Pre{
int point, edge;
}pre[maxn];
inline void add(int x,int y,int z){
e[++tot].to = y;
e[tot].next = head[x];
e[tot].val = z;
head[x] = tot;
}
inline int rd(){
int f = 1, s = 0; char c = getchar();
for(;!isdigit(c);c = getchar()) if(c == '-') f = -1;
for(; isdigit(c);c = getchar()) s = (s << 3) + (s << 1) + c - '0';
return f * s;
}
inline bool bfs(){
queue <int> q;
memset(vis, 0, sizeof(vis));
memset(pre,-1, sizeof(pre));
vis[s] = true; q.push(s);
while(!q.empty()){
int now = q.front(); q.pop();
for(int i = head[now]; i; i = e[i].next){
int to = e[i].to;
if(!vis[to] && e[i].val){
pre[to].point = now;
pre[to].edge = i;
if(to == t) return true;
vis[to] = 1;
q.push(to);
}
}
}
}
inline int EK(){
int ans = 0;
while(bfs()){
int mi = inf;
for(int i = t; i != s; i = pre[i].point) mi = mi < e[pre[i].edge].val ? mi : e[pre[i].edge].val;
for(int i = t; i != s; i = pre[i].point){
e[pre[i].edge].val -= mi;
e[pre[i].edge^1].val += mi;
}
ans += mi;
}
return ans;
}
inline void main(){
n = rd(), m = rd(), s = rd(), t = rd();
for(int x, y, z, i = 1; i <= m; i++)
x = rd(), y = rd(), z = rd(), add(x,y,z), add(y,x,0);
printf("%d",EK());
return;
}
}
int main(){
_lgl::main();
return 0;
}
|