5832: 7.4 最小费用最大流
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:14
解决:7
题目描述
在实际应用中,不仅要考虑流量,还要考虑费用。例如在网络布线工程中有很多中电缆,电缆的粗细不同,流量和费用也不同。如果全部使用较粗的电缆,则造价太高;如果全部使用较细的电缆,则流量满足不了要求。我们希望建立一个费用最小、流量最大的网络,即最小费用最大流。
输入
样例组数
t ( 0 < t < 10 )
节点个数和边数
n m ( 0 < n < 100 ) ( 0 < m < 10000 )
依次输入两个节点和容量、单位容量的费用 ( 0 < w, c < 100 )
u1 v1 w1 c1
u2 v2 w2 c2
...
um vm wm cm
t ( 0 < t < 10 )
节点个数和边数
n m ( 0 < n < 100 ) ( 0 < m < 10000 )
依次输入两个节点和容量、单位容量的费用 ( 0 < w, c < 100 )
u1 v1 w1 c1
u2 v2 w2 c2
...
um vm wm cm
输出
网络的最小费用和最大流值
minCost ans
minCost ans
样例输入 复制
1
6 10
1 3 4 7
1 2 3 1
2 5 4 5
2 4 6 4
2 3 1 1
3 5 3 6
3 4 5 3
4 6 7 6
5 6 3 2
5 4 3 3
样例输出 复制
88 7