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

1591_有源汇有上下界最大流

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

摘要:

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

Pro.ID

1591

Title

有源汇有上下界最大流

Title链接

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

AC

Submit

Ratio

80.00%

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

描述

这是一道模板题。

n 个点，m 条边，每条边 e 有一个流量下界 lower(e) 和流量上界 upper(e) ，给定源点s 与汇点t ，求源点到汇点的最大流。

输入

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

之后的 m 行，每行四个整数 s 、t 、lower 、upper 。

1 ≤ n ≤ 202 , 1 ≤ m ≤ 9999

输出

Description

这是一道模板题。

n 个点，m 条边，每条边 e 有一个流量下界 lower(e) 和流量上界 upper(e) ，给定源点s 与汇点t ，求源点到汇点的最大流。

Input

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

之后的 m 行，每行四个整数 s 、t 、lower 、upper 。

1 ≤ n ≤ 202 , 1 ≤ m ≤ 9999

Output

如果无解，输出一行 please go home to sleep。

否则输出最大流。

Sample Input

10 15 9 10
9 1 17 18
9 2 12 13
9 3 11 12
1 5 3 4
1 6 6 7
1 7 7 8
2 5 9 10
2 6 2 3
2 7 0 1
3 5 3 4
3 6 1 2
3 7 6 7
5 10 16 17
6 10 10 11
7 10 14 15

Sample Output

Author

John

样例输入