最小费用流

题目描述

给定一个图，每条边有容量和费用，使用每条边的单位流量需要支付特定的费用。给定源点 1 和汇点 n，求图的最大流和最大流需要支付的最小费用。

输入

第一行两个整数 n、m，表示有 n 个点 m 条边。

从第二行开始的之后 m 行，每行四个整数 s_i、t_i、c_i、w_i 表示一条从 s_i 到 t_i 的边，容量为 c_i，单位流量需要支付的费用为 w_i。

输出

一行两个整数，分别表示最大流和最大流需要支付的最小费用。

样例如同所示，最小费用流为：
1->4 流量20 费用20 × 3 =60;
1->2->4 流量20 费用20×(2+1)=60;
1->2->3->4 流量10 费用10×(2+9+5)=140;;
最大流量为20+20+10=50；总费用为60+60+140=280；

样例

提示

1 \leq n \leq 400, 0 \leq m \leq 15000, w_i\geq 0，保证输入数据、中间结果以及答案在 32 位有符号整数范围内。

来源

模板