/ 模板 / 题库 /

网络流

网络流

描述

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

格式

输入格式

第一行包含四个正整数NNMMSSTT,分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来MM行每行包含三个正整数uiu_iviv_iwiw_i,表示第ii条有向边从uiu_i出发,到达viv_i,边权为wiw_i(即该边最大流量为wiw_i)。

输出格式

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

样例

样例输入

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

样例输出

50

限制

N10000N\le 10000M100000M\le 100000

信息

难度
7
分类
网络流 点击显示
标签
递交数
101
已通过
6
通过率
6%
上传者

相关

在下列训练计划中:

模板训练