【模板】网络最大流

题目描述

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

输入输出格式

输入格式


第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个数、源点序号、汇点序号。 接下来M行每行包含三个正整数ui、vi、wi,表示第i条有向边从ui出发,到达vi,边权为wi(即该边最大流量为wi)

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

50

说明

时空限制:1000ms,128M 数据规模: 对于30%的数据:N<=10,M<=25 对于70%的数据:N<=200,M<=1000 对于100%的数据:N<=10000,M<=100000 样例说明: ![](https://cdn.luogu.com.cn/upload/pic/2262.png) 题目中存在3条路径: 4-->2-->3,该路线可通过20的流量 4-->3,可通过20的流量 4-->2-->1-->3,可通过10的流量(边4-->2之前已经耗费了20的流量) 故流量总计20+20+10=50。输出50。