noip2010普及组复赛最后一题flow

题目描述

给定一个 $n$ 个点 $m$ 条边的网络流图，每条边有一个下界 $l_i$ 和一个上界 $r_i$，以及一个费用 $c_i$。要求你求出从源点到汇点的最小费用流，使得每条边的流量都满足其下界和上界限制。

输入格式

第一行两个整数 $n,m$，表示点数和边数。

接下来 $m$ 行，每行 $3$ 个整数 $a_i,b_i,l_i,r_i,c_i$，表示一条从 $a_i$ 到 $b_i$，下界为 $l_i$，上界为 $r_i$，费用为 $c_i$ 的边。

输出格式

输出一个整数，表示所求的最小费用流。如果不存在满足限制条件的流，输出 $-1$。

数据范围

$1 \le n,m \le 1000$, $0 \le l_i \le r_i \le 10^3$, $0 \le c_i \le 10^3$

样例

输入样例：

3 3 1 2 1 2 1 2 3 1 3 2 1 3 0 2 2

输出样例：

3

算法1

最小费用最大流

算法2

(暴力枚举) $O(n^4)$

枚举边的流量，检查是否满足下界和上界条件，再计算费用即可。

时间复杂度

参考文献

C++ 代码

算法3

(暴力枚举)

blablabla

时间复杂度

参考文献

C++ 代