UOJ Logo Universal Online Judge

UOJ

#487. 最小费用最大流

附件下载 统计

给你一张 $n$ 个点 $m$ 条边构成的有向图 $G=(V, E)$,其中点从 $1$ 到 $n$ 编号,第 $i$ 条边的起点为 $from(i)$,终点为 $to(i)$,有容量 $cap(i)$ 和费用 $cost(i)$ 两个属性。并且,图中存在两个特殊点,源点 $s$ 和汇点 $t$,$s$ 点没有入边,$t$ 点没有出边。

定义流函数 $f:E\rightarrow N$ 为满足以下条件的任一函数(即 $f(i)$ 表示 $i$ 这条边的流量):

  1. $\forall i\in E, 0\le f(i)\le cap(i)$(每条边的流量不超过容量)。

  2. $\forall u\in (V\setminus\{s, t\}), \sum\limits_{from(i) = u\ }f(i)=\sum\limits_{to(i) = u\ }f(i)$(除源汇外每个点的流出量等于流入量)。

定义一个流函数的流量为 $s$ 流出的流量:$flow(f)=\sum_{from(i)=s\ \ \,}f(i)$。

定义一个流函数的总费用为每条边的流量与费用乘积之和:$totalcost(f)=\sum_{i\in E\;}f(i) \cdot cost(i)$。

请求出最大流($flow(f)$ 的最大值),以及最大流前提下的最小费用(即 $\min\{totalcost(f)|flow(f)=\max\{flow(i)|i\text{ is a flow of }G\}\}$)。

输入格式

输入的第一行包含四个正整数 $n$, $m$, $s$, $t$,分别表示图的点数和边数,源点和汇点。

接下来 $m$ 行中的第 $i$ 行包含四个整数 $from(i)$, $to(i)$, $cap(i)$, $cost(i)$,分别表示图中第 $i$ 条边的起点,终点,容量,费用。

输出格式

输出包含两个整数,分别表示最大流和最大流前提下的最小费用。

样例一

input

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

output

50 280

explanation

用 $f(u, v)$ 代指 $u$ 到 $v$ 这条边的流量,那么取到最大流前提下的最小费用时,$f(4, 2)=30$, $f(4, 3)=20$, $f(2, 3)=20$, $f(2, 1)=10$, $f(1, 3)=10$ 。

样例二

input

3 1 1 3
2 2 1 -1

output

0 -1

explanation

一个合法的流只需满足容量限制与流量平衡,一个与 $s$, $t$ 不连通的环也可以有流量。(如果不允许这种不连通负环计入费用的话,可以规约到哈密顿回路问题。)

限制与约定

对于 $100\%$ 的数据,$1\le n, m\le 500$,$1\le s, t\le n$,$s\ne t$,$1\le from(i), to(i)\le n$,$from(i)\ne t$,$to(i)\ne s$,$1\le cap(i)\le 10^9$,$-2\cdot 10^6\le cost(i)\le 2\cdot 10^6$。

时间限制:$5\texttt{s}$

空间限制:$512\texttt{MB}$

提示

常见费用流算法的复杂度为 $O(nmf)$ (其中 $f$ 表示最大流的大小),可能无法通过此题。

一种可行的解决方案是使用 基于 Capacity Scaling 的弱多项式复杂度最小费用流算法