#P2188. 无源汇上下界可行流
无源汇上下界可行流
无源汇上下界可行流
题目描述
给定一个包含 个点 条边的有向图,每条边都有一个流量下界和流量上界。
求一种可行方案使得在所有点满足流量平衡条件的前提下,所有边满足流量限制。
本题不唯一的可行方案输出任意一种即可(使用 Special Judge)。
输入格式
第一行包含两个整数 和 。
接下来 行,每行包含四个整数 ,表示点 和 之间存在一条有向边,该边的流量下界为 ,流量上界为 。
点编号从 到 。
输出格式
如果存在可行方案,则第一行输出 YES,接下来 行,每行输出一个整数,其中第 行的整数表示输入的第 条边的流量。
如果不存在可行方案,直接输出一行 NO。
如果可行方案不唯一,则输出任意一种方案即可。
样例
输入样例 1
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
输出样例 1
YES
1
2
3
2
1
1
(方案不唯一,任何满足条件的方案均可)
输入样例 2
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
输出样例 2
NO