P14579 【模板】有源汇上下界最大流

题目描述

给你一个 $n$ 个点、$m$ 条有向边的有向图 $G$,每条边有流量下界 $l_i$ 和流量上界 $r_i$,以及源点 $s$ 和汇点 $t$。 求出源点 $s$ 到汇点 $t$ 的最大流量或报告无解。

输入格式

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

输出格式

输出源点 $s$ 到汇点 $t$ 的最大流量,若无解输出 `N`。

说明/提示

**【样例解释 #1】** ![](https://cdn.luogu.com.cn/upload/image_hosting/o896fsx0.png) 其中 $1$ 号点为源点,$5$ 号点为汇点。 **【数据范围】** 图可能会有重边和自环。 对于所有测试数据:$1\leq n\leq 10^3$,$1\leq s,t\leq n$,$1\leq m\leq 10^4$,$1\leq u_i,v_i\leq n$,$0\leq l_i\leq r_i\leq 10^5$。 保证 $s\neq t$。对于任意 $i$ 保证 $s\neq v_i$,$t\neq u_i$。