You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

输入格式

第一行包含四个正整数 $n,m,s,t$，分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来 $m$ 行每行包含三个正整数 $u_i,v_i,w_i$，表示第 $i$ 条有向边从 $u_i$ 出发，到达 $v_i$，边权为 $w_i$（即该边最大流量为 $w_i$）。

输出格式

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

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

50

提示

样例输入输出 1 解释

题目中存在 $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$。
• 对于 $100\%$ 的数据，保证 $1 \leq n\leq200$，$1 \leq m\leq 5000$，$0 \leq w\lt 2^{31}$。