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

1592_有源汇有上下界最小流

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

摘要:

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

Pro.ID

1592

Title

有源汇有上下界最小流

Title链接

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

AC

Submit

Ratio

66.67%

时间&空间限制

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 ≤ 50003 , 1 ≤ m ≤ 125003

输出

Description

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

Input

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

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

1 ≤ n ≤ 50003 , 1 ≤ m ≤ 125003

Output

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

否则输出最小流。

Sample Input

7 12 6 7
6 1 0 2147483647
1 7 0 2147483647
6 2 0 2147483647
2 7 0 2147483647
6 3 0 2147483647
3 7 0 2147483647
6 4 0 2147483647
4 7 0 2147483647
6 5 0 2147483647
5 7 0 2147483647
5 1 1 2147483647
3 4 1 2147483647

Sample Output

Author

John

样例输入

样例输出

提示