题目描述
这是一道模板题。
给定一个图，每条边有容量和费用，使用每条边的单位流量需要支付特定的费用。给定源点
1
1 和汇点
n
n，求图的最大流和最大流需要支付的最小费用。
输入
第一行两个整数
n
n、
m
m，表示有
n
n 个点
m
m 条边。
从第二行开始的之后
m
m 行，每行四个整数
s_i
si
、
t_i
ti
、
c_i
ci
、
w_i
wi
表示一条从
s_i
si
到
t_i
ti
的边，容量为
c_i
ci
，单位流量需要支付的费用为
w_i
wi
。
输出
一行两个整数，分别表示最大流和最大流需要支付的最小费用。
样例输入
8 23
2 3 2147483647 1
1 3 1 1
2 4 2147483647 2
1 4 1 2
2 8 2 0
3 5 2147483647 3
1 5 1 3
3 6 2147483647 4
1 6 1 4
3 8 2 0
3 2 2147483647 0
4 6 2147483647 5
1 6 1 5
4 7 2147483647 6
1 7 1 6
4 8 2 0
4 2 2147483647 0
5 8 0 0
5 2 2147483647 0
6 8 0 0
6 2 2147483647 0
7 8 0 0
7 2 2147483647 0
样例输出
6 24
提示
数据范围与提示
1 \leq n \leq 400, 0 \leq m \leq 15000, w_i\geq 0
1≤n≤400,0≤m≤15000,wi
≥0，保证输入数据、中间结果以及答案在 32 位有符号整数范围内。
来源/分类
费用流 网络流