P14578 【模板】无源汇上下界可行流

题目描述

给你一个 $n$ 个点、$m$ 条有向边的有向图 $G$,每条边有流量下界 $l_i$ 和流量上界 $r_i$。 你需要判断是否存在一种方案使得每条边的流量 $w_i$ 满足流量限制 $l_i\leq w_i\leq r_i$,且每个点流量平衡,即每个点流入流量等于流出流量。 构造一组满足上述限制的流量方案或报告无解。

输入格式

第一行两个正整数 $n,m$,表示图 $G$ 的点数和边数。 接下来 $m$ 行每行四个非负整数 $u_i,v_i,l_i,r_i$,分别表示每条有向边的起点和终点,以及流量下界和上界。 图可能会有重边和自环。

输出格式

若存在可行方案,第一行输出 `Yes`,接下来 $m$ 行每行一个非负整数 $w_i$,表示第 $i$ 条边的实际流量。 若不存在可行方案,输出 `No`。

说明/提示

**【样例解释 #1】** ![](https://cdn.luogu.com.cn/upload/image_hosting/eijm9ax8.png) 图为样例输出的流量方案。 **【数据范围】** 图可能会有重边和自环。 对于所有测试数据:$1\leq n\leq 10^3$,$1\leq m\leq 10^4$,$1\leq u_i,v_i\leq n$,$0\leq l_i\leq r_i\leq 10^5$。