P4070 - 最小费用流

时间限制：1000 ms 内存限制：128 MB

上传者：

提交：14 通过：0

提交提交记录讨论统计

这是一道模板题。

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

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

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

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

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

网络流

4070: 最小费用流

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签