最小费用最大流
给你一张 $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$ 这条边的流量）：
$\forall i\in E, 0\le f(i)\le cap(i)$（每条边的流量不超过容量）。
$\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$ 条边的起点，终点，容量，费用。
输出格式
输出包含两个整数，分别表示最大流和最大流前提下的最小费用。
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
用 $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$ 。
3 1 1 3
2 2 1 -1
0 -1
一个合法的流只需满足容量限制与流量平衡，一个与 $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 的弱多项式复杂度最小费用流算法 。