题目描述

给定一张 $n$ 个点 $m$ 条边的费用网络，源为 $s$ 且汇为 $t$ ，求其最小费用最大流。

注意存在费用为负的边和总费用为负的环。

注意，本题中允许一个不经过 $s,t$ 的环整体加上一个流量。事实上，若不允许这种情况的出现，则哈密顿路可以归约为这个问题。

输入格式

输入第一行包括四个正整数 $n,m,s,t$。

第 $2$ 到 $m+1$ 行，每行四个整数 $x_i,y_i,f_i,v_i$，表示存在一条 $x_i$ 到 $y_i$ 的边，流量为 $f_i$，费用为 $v_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

5 7 1 5
1 3 2 4
1 2 2 3
3 5 2 2
3 2 1 -1
2 4 2 -2
4 3 1 -1
4 5 1 3

3 12

提示

对于 $100\%$ 的数据：$1\leq n\leq 200$，$1\leq m\leq {10}^{4}$，$0\leq f_i,|v_i|\leq 100$。

注：不知道消圈算法能不能过，由于数据分档，即使不能过应该也能拿到一定的分数。