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

1595_最大流加强版

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

摘要:

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

Pro.ID

1595

Title

最大流加强版

Title链接

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

AC

Submit

Ratio

23.53%

时间&空间限制

Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)

描述

这是一道模板题。

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

输入

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

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

1 ⩽ n ⩽ 1200 , 1 ⩽ m ⩽ 120000 , 1 ⩽ c ⩽ 2³¹ − 1

常用网络流算法的复杂度为 O(n²m) ，请尽量优化算法。

输出

Description

这是一道模板题。

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

Input

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

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

1 ⩽ n ⩽ 1200 , 1 ⩽ m ⩽ 120000 , 1 ⩽ c ⩽ 2³¹ − 1

常用网络流算法的复杂度为 O(n²m) ，请尽量优化算法。

Output

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

Sample Input

Sample #1
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 #2
10 16 1 2
1 3 2
1 4 2
5 2 2
6 2 2
3 5 1
3 6 1
4 5 1
4 6 1
1 7 2147483647
9 2 2147483647
7 8 2147483647
10 9 2147483647
8 5 2
8 6 2
3 10 2
4 10 2