【模板】网络最大流

题目描述

如题,给出一个网络图,以及其源点和汇点,求出其网络最大流。

输入输出格式

输入格式


第一行包含四个正整数 $n,m,s,t$,分别表示点的个数、有向边的个数、源点序号、汇点序号。 接下来M行每行包含三个正整数 $u_i,v_i,w_i$,表示第 $i$ 条有向边从 $u_i$ 出发,到达 $v_i$,边权为 $w_i$(即该边最大流量为 $w_i$)。

输出格式


一行,包含一个正整数,即为该网络的最大流。

输入输出样例

输入样例 #1

4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40

输出样例 #1

50

说明

#### 样例输入输出 1 解释 ![](https://cdn.luogu.com.cn/upload/pic/2262.png) 题目中存在 $3$ 条路径: - $4\to 2\to 3$,该路线可通过 $20$ 的流量。 - $4\to 3$,可通过 $20$ 的流量。 - $4\to 2\to 1\to 3$,可通过 $10$ 的流量(边 $4\to 2$ 之前已经耗费了 $20$ 的流量)。 故流量总计 $20+20+10=50$。输出 $50$。 --- #### 数据规模与约定 - 对于 $30\%$ 的数据,$n\leq10,m\leq25$ - 对于 $70\%$ 的数据,$n\leq200,m\leq1000$ - 对于 $100\%$ 的数据,$1 \leq n\leq10^4$,$1 \leq m \leq 10^5$,$1 \leq w\leq 10^9$,保证答案在 32 位带符号整形范围内。