Pro.ID1577 Title最小费用流 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1577 AC11 Submit14 Ratio78.57% 时间&空间限制描述这是一道模板题。 给定一个图,每条边有容量和费用,使用每条边的单位流量需要支付特定的费用。给定源点 1 和汇点 n ,求图的最大流和最大流需要支付的最小费用。 输入第一行两个整数 n 、m ,表示有 n 个点 m 条边。 从第二行开始的之后 m 行,每行四个整数 si 、ti 、ci 、wi 表示一条从 si 到 ti 的边,容量为 ci ,单位流量需要支付的费用为 wi 。 1 ≤ n ≤ 400 , 0 ≤ m ≤ 15000 , wi ≥ 0,保证输入数据、中间结果以及答案在 32 位有符号整数范围内。 输出Description 这是一道模板题。 给定一个图,每条边有容量和费用,使用每条边的单位流量需要支付特定的费用。给定源点 1 和汇点 n ,求图的最大流和最大流需要支付的最小费用。 Input 第一行两个整数 n 、m ,表示有 n 个点 m 条边。 从第二行开始的之后 m 行,每行四个整数 si 、ti 、ci 、wi 表示一条从 si 到 ti 的边,容量为 ci ,单位流量需要支付的费用为 wi 。 1 ≤ n ≤ 400 , 0 ≤ m ≤ 15000 , wi ≥ 0,保证输入数据、中间结果以及答案在 32 位有符号整数范围内。 Output 一行两个整数,分别表示最大流和最大流需要支付的最小费用。 Sample Input 8 23 Sample Output 6 24 Author 样例输入8 23 样例输出6 24 提示作者 |