10369: Dinic/ISAP求最小割
[Creator : ]
Description
给定一个包含 $n$ 个点 $m$ 条边的有向图，并给定每条边的容量，边的容量非负。
图中可能存在重边和自环。求从点 $S$ 到点 $T$ 的最小割。
图中可能存在重边和自环。求从点 $S$ 到点 $T$ 的最小割。
Input
第一行包含四个整数 $n,m,S,T$。
接下来 $m$ 行，每行三个整数 $u,v,c$，表示从点 $u$ 到点 $v$ 存在一条有向边，容量为 $c$。
点的编号从 $1$ 到 $n$。
接下来 $m$ 行，每行三个整数 $u,v,c$，表示从点 $u$ 到点 $v$ 存在一条有向边，容量为 $c$。
点的编号从 $1$ 到 $n$。
Output
输出点 $S$ 到点 $T$ 的最小割。
如果从点 $S$ 无法到达点 $T$ 则输出 $0$。
如果从点 $S$ 无法到达点 $T$ 则输出 $0$。
Constraints
$2≤n≤10000$
$1≤m≤100000$
$0≤c≤10000$
$S≠T$
$1≤m≤100000$
$0≤c≤10000$
$S≠T$
Sample 1 Input
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
Sample 1 Output
14
Sample 2 Input
5 10 2 5
1 2 0
3 1 3
3 4 4
5 3 0
5 5 1
5 5 1
3 5 4
2 2 0
1 5 0
4 2 1
Sample 2 Output
0