logo AlgoBeat OnlineJudge
登录 注册

#214473. 【模板】有源汇上下界最小流

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

给你一个 个点、 条有向边的有向图 ,每条边有流量下界 和流量上界 ,以及源点 和汇点

求出源点 到汇点 的最小流量或报告无解。

输入格式

第一行两个正整数 ,表示图 的点数和边数,以及源点编号和汇点编号。

接下来 行每行四个正整数 ,分别表示每条有向边的起点和终点,以及流量下界和上界。

图可能会有重边和自环。

输出格式

输出源点 到汇点 的最小流量,若无解输出 N

样例

样例输入 1

6 7 1 5
1 2 3 5
2 3 3 4
3 4 5 6
1 4 1 5
4 5 0 100000
6 3 0 1
4 6 1 2

样例输出 1

5

样例输入 2

6 6 4 1
4 1 0 5
4 2 0 6
4 3 0 7
2 2 3 3
5 6 1 1
6 5 2 2

样例输出 2

N

数据范围与提示

【样例解释 #1】

其中 号点为源点, 号点为汇点。

【数据范围】

图可能会有重边和自环。

对于所有测试数据:

保证 。对于任意 保证