1416-最小费用最大流


    内存限制:64MB 时间限制:1000ms 特判: No

    通过数:2 提交数:5 难度:6


题目描述:

在实际应用中,不仅要考虑流量,还要考虑费用。例如在网络布线工程中有很多中电缆,电缆的粗细不同,流量和费用也不同。如果全部使用较粗的电缆,则造价太高;如果全部使用较细的电缆,则流量满足不了要求。我们希望建立一个费用最小、流量最大的网络,即最小费用最大流。


输入描述:

第一行是一个整型数C(C<100)表示共有C组测试数据。
每组测试数据第一行输入结点个数n和边数m(1<=n<=50,1<=m<=2500)。
接下来m行,每行4个数,两个结点u,v及边(u--v)的容量w,单位容量费用c(1<=u,v<=50,1<=w,c<=100)。

输出描述:

对于每一组输入,输出网络的最小费用和最大流值。
每组的输出占一行。

样例输入:

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

提示:


上传者:rainflychxy

书中题目链接,请点击上面链接访问!

公告

    欢迎使用NYOJ2.0!