#O1106. 最小费用最大流

最小费用最大流

题目描述

给出一个有 nn 个点、mm 条有向边的网络,源点为 SS,汇点为 TT。每条边有容量 cic_i 和单位费用 wiw_i。求该网络的最大流,并在最大流下求最小总费用。

输入格式

第一行四个整数 n,m,S,Tn,m,S,T。

接下来 mm 行,每行四个整数 ui,vi,ci,wiu_i,v_i,c_i,w_i,表示从 uiu_i 到 viv_i 有一条容量为 cic_i、单位费用为 wiw_i 的有向边。

输出格式

一行两个整数,依次为最大流与最小总费用,用空格分隔。

样例 #1

样例输入 #1

4 5 1 4
1 2 2 1
1 3 1 2
2 3 1 1
2 4 2 3
3 4 1 4

样例输出 #1

3 14

数据规模与约定

数据范围 说明
1≤n≤2001 \le n \le 200 点数
1≤m≤20001 \le m \le 2000 边数
1≤ci≤1031 \le c_i \le 10^3 容量
0≤wi≤1030 \le w_i \le 10^3 单位费用
  • 最大流与最小费用均为整数,可用 32 位整型存储。
  • 输入保证 S≠TS \ne T,且 SS 到 TT 存在至少一条路径。