题目描述

给定 $n$ 个点， $m$ 条边，给定每条边的容量，求点 $s$ 到点 $t$ 的最大流。

注意，图可能存在重边。

输入格式

第一行四个整数 $n$，$m$，$s$，$t$。

接下来的 $m$ 行，每行三个整数 $u$，$v$，$c$，表示从 $u$ 到 $v$，容量为 $c$ 的一条边。

输出格式

输出一行一个整数，表示从 $s$ 到 $t$ 的最大流。

7 14 1 7
1 2 5
1 3 6
1 4 5
2 3 2
2 5 3
3 2 2
3 4 3
3 5 3
3 6 7
4 6 5
5 6 1
6 5 1
5 7 8
6 7 7

14

10 30 3 7
10 2 18652
8 9 2560
8 9 13734
5 6 23138
9 7 29606
5 8 21673
1 9 11596
3 2 9441
3 7 4829
5 8 24437
1 2 31111
4 10 26213
2 7 31808
1 9 10841
6 8 10758
3 5 11887
4 2 1362
4 1 18182
4 8 18156
10 6 11015
2 7 2640
10 6 27726
10 6 21615
5 1 5959
3 1 19857
5 4 1862
8 9 13830
3 10 22152
4 10 5221
5 2 24065

68166

6 18 4 6
4 3 31298
4 5 25605
1 6 8332
1 6 1205
2 3 15950
4 3 1418
1 6 5329
1 6 29907
5 6 22281
1 2 12609
4 1 4033
1 2 12122
4 5 5997
5 6 19507
1 5 19306
2 6 978
5 6 26343
5 3 23224

35635

提示

对于所有数据，$1 \le n \le 100$，$1 \le m \le 5000$，$0 \le c \le 2 ^ {31} - 1$。