#P3381. 【模板】最小费用最大流

【模板】最小费用最大流

题目描述

给出一个包含 nn 个点和 mm 条边的有向图(下面称其为网络) G=(V,E)G=(V,E),该网络上所有点分别编号为 1n1 \sim n,所有边分别编号为 1m1\sim m,其中该网络的源点为 ss,汇点为 tt,网络上的每条边 (u,v)(u,v) 都有一个流量限制 w(u,v)w(u,v) 和单位流量的费用 c(u,v)c(u,v)

你需要给每条边 (u,v)(u,v) 确定一个流量 f(u,v)f(u,v),要求:

  1. 0f(u,v)w(u,v)0 \leq f(u,v) \leq w(u,v)(每条边的流量不超过其流量限制);
  2. p{V{s,t}}\forall p \in \{V \setminus \{s,t\}\}(i,p)Ef(i,p)=(p,i)Ef(p,i)\sum_{(i,p) \in E}f(i,p)=\sum_{(p,i)\in E}f(p,i)(除了源点和汇点外,其他各点流入的流量和流出的流量相等);
  3. (s,i)Ef(s,i)=(i,t)Ef(i,t)\sum_{(s,i)\in E}f(s,i)=\sum_{(i,t)\in E}f(i,t)(源点流出的流量等于汇点流入的流量)。

定义网络 GG 的流量 F(G)=(s,i)Ef(s,i)F(G)=\sum_{(s,i)\in E}f(s,i),网络 GG 的费用 C(G)=(i,j)Ef(i,j)×c(i,j)C(G)=\sum_{(i,j)\in E} f(i,j) \times c(i,j)

你需要求出该网络的最小费用最大流,即在 F(G)F(G) 最大的前提下,使 C(G)C(G) 最小。

输入格式

输入第一行包含四个整数 n,m,s,tn,m,s,t,分别代表该网络的点数 nn,网络的边数 mm,源点编号 ss,汇点编号 tt

接下来 mm 行,每行四个整数 ui,vi,wi,ciu_i,v_i,w_i,c_i,分别代表第 ii 条边的起点,终点,流量限制,单位流量费用。

输出格式

输出两个整数,分别为该网络的最大流 F(G)F(G),以及在 F(G)F(G) 最大的前提下,该网络的最小费用 C(G)C(G)

4 5 4 3
4 2 30 2
4 3 20 3
2 3 20 1
2 1 30 9
1 3 40 5
50 280

提示

对于 100%100\% 的数据,1n5×1031 \leq n \leq 5\times 10^31m5×1041 \leq m \leq 5 \times 10^41s,tn1 \leq s,t \leq nuiviu_i \neq v_i0wi,ci1030 \leq w_i,c_i \leq 10^3,且该网络的最大流和最小费用 2311\leq 2^{31}-1

输入数据随机生成。