2190

2190. 有源汇上下界最小流

题目

给定一个包含 $n$ 个点 $m$ 条边的 有向 图，每条边都有一个流量下界和流量上界。

给定源点 $S$ 和汇点 $T$，求源点到汇点的最小流。

注意，为了方便，本题做出如下约定：

• 可行流流量 = 从源点流出的流量 - 流入源点的流量，可以为负值。
• 例如，当 $S \rightarrow T$ 的流量为 $0$，$T \rightarrow S$ 的流量为 $10$ 时，$S \rightarrow T$ 的流量为 $-10$。

输入格式

第一行包含四个整数 $n,m,S,T$。

接下来 $m$ 行，每行包含四个整数 $a,b,c,d$ 表示点 $a$ 和 $b$ 之间存在一条有向边，该边的流量下界为 $c$，流量上界为 $d$。

点编号从 $1$ 到 $n$。

输出格式

输出一个整数表示最小流。

如果无解，则输出 No Solution。

数据范围

$1 \le n \le 50003$,

$1 \le m \le 125003$,

$1 \le a,b \le n$,

$0 \le c \le d \le 2147483647$,

数据保证答案不超过 $int$ 范围。

输入样例：

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

输出样例：

2

题解