U147037 【模板】最小费用最大流 2

请注意，能通过本题的代码**不保证**能通过 [【模板】最小费用最大流](/problem/P3381)。

给出一个包含 $n$ 个点和 $m$ 条边的有向图（下面称其为网络）$G=(V,E)$，该网络上所有点分别编号为 $1 \sim n$，所有边分别编号为 $1\sim m$，其中该网络的源点为 $s$，汇点为 $t$。网络上的每条边 $(u,v)$ 都有一个流量限制 $w(u,v)$ 和单位流量的费用 $c(u,v)$。该网络满足，没有以源点为终点的边，也没有以汇点为起点的边。 你需要给每条边 $(u,v)$ 确定一个流量 $f(u,v)$，要求： - $0 \leq f(u,v) \leq w(u,v)$（每条边的流量不超过其流量限制）； - $\forall p \in \{V \setminus \{s,t\}\}$，$\sum_{(i,p) \in E}f(i,p)=\sum_{(p,i)\in E}f(p,i)$（除了源点和汇点外，其他各点流入的流量和流出的流量相等）； - $\sum_{(s,i)\in E}f(s,i)=\sum_{(i,t)\in E}f(i,t)$（源点流出的流量等于汇点流入的流量）。 定义网络 $G$ 的流量 $F(G)=\sum_{(s,i)\in E}f(s,i)$，网络 $G$ 的费用 $C(G)=\sum_{(i,j)\in E} f(i,j) \times c(i,j)$。 你需要求出该网络的最小费用最大流，即在 $F(G)$ 最大的前提下，使 $C(G)$ 最小。

输入第一行包含四个整数 $n,m,s,t$，分别代表该网络的点数 $n$，网络的边数 $m$，源点编号 $s$，汇点编号 $t$。 接下来 $m$ 行，每行四个整数 $u_i,v_i,w_i,c_i$，分别代表第 $i$ 条边的起点，终点，流量限制，单位流量费用。

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

### 样例解释 1 在接下来的样例解释中，用 $(w_i,c_i)$ 代表一条流量限制为 $w_i$，单位流量费用为 $c_i$ 的边。  使该网络在达到最大流的前提下，取得最小费用的方案如下（用 $x/y$ 表示该边的流量为 $x$，流量上限为 $y$）：  ### 样例解释 2  使该网络在达到最大流的前提下，取得最小费用的方案如下：  注意在满足流量平衡原则的前提下，与 $s,t$ 不相连的边也可以有流量。 另外请注意题目中 $F(G)$ 和 $C(G)$ 的定义，$F(G)$ 只计算从 $s$ 点流到 $t$ 点的流量，而 $C(G)$ 不仅计算从 $s$ 点流到 $t$ 点的流量的费用，也计算了与 $s,t$ 不相连的边的流量的费用。 ### 子任务 所有测试点均满足：$1 \leq n,m \leq 500$，$1 \leq s,t \leq n$，$s \neq t$，$u_i \neq t$，$v_i \neq s$，$1 \leq w_i \leq 10^9$，$|c_i| \leq 5 \times 10^6$，**不保证**图中无重边和自环。 - 子任务 1（50 分）：$n, m \leq 100$，$w_i \leq 5000$。 - 子任务 2（50 分）：无附加约束。