#175. #115. 无源汇有上下界可行流
-
ID: 175
传统题
1000ms
256MiB
尝试: 0
已通过: 0
难度: (无)
上传者:
#115. 无源汇有上下界可行流
说明
这是一道模板题。
n n n 个点，m m m 条边，每条边 e e e 有一个流量下界 lower(e) \text{lower}(e) lower(e) 和流量上界 upper(e) \text{upper}(e) upper(e)，求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。
输入格式
第一行两个正整数 n n n、m m m。
之后的 m m m 行，每行四个整数 s s s、t t t、lower \text{lower} lower、upper \text{upper} upper。
输出格式
如果无解，输出一行 NO。
否则第一行输出 YES，之后 m m m 行每行一个整数，表示每条边的流量。
样例
样例输入 1
4 6
1 2 1 2
2 3 1 2
3 4 1 2
4 1 1 2
1 3 1 2
4 2 1 2样例输出 1
NO样例输入 2
4 6
1 2 1 3
2 3 1 3
3 4 1 3
4 1 1 3
1 3 1 3
4 2 1 3样例输出 2
YES
1
2
3
2
1
1数据范围与提示
1≤n≤200,1≤m≤10200 1 \leq n \leq 200, 1 \leq m \leq 10200 1≤n≤200,1≤m≤10200