同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1576_最大流

2022-5-16 18:17| 发布者: Hocassian| 查看: 70| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-89503987440500-Problem List-采集的数据-后羿采集器.html

Pro.ID

1576

Title

最大流

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1576

AC

Submit

Ratio

23.94%

时间&空间限制

Time Limit: 60000/30000 MS (Java/Others) Memory Limit: 562144/562144 K (Java/Others)

描述

这是一道模板题。

给定 n 个点，m 条边，给定每条边的容量，求从点 s 到点 t 的最大流。

输入

第一行四个整数 n, m, s, t 。

接下来的 m 行，每行三个整数 u, v, c 表示 u 到 v ，流量为 c 的一条边。

1 ⩽ n ⩽ 10⁶ ,1 ⩽ m ⩽ 4×10⁶ , 0 ⩽ c ⩽ 2³¹-1

输出

Description

这是一道模板题。

给定 n 个点，m 条边，给定每条边的容量，求从点 s 到点 t 的最大流。

Input

第一行四个整数 n, m, s, t 。

接下来的 m 行，每行三个整数 u, v, c 表示 u 到 v ，流量为 c 的一条边。

1 ⩽ n ⩽ 10⁶ ,1 ⩽ m ⩽ 4×10⁶ , 0 ⩽ c ⩽ 2³¹-1

Output

输出点 s 到点 t 的最大流。

Sample 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 Output

Author

John

样例输入