Hide

Problem D
Minimum Cost Maximum Flow

Input

The first line of input contains a line contains a line with four non-negative integers, $2 \le n \le 250$, $0 \le m \le 5\, 000$, $0 \le s \le n-1$ and $0 \le t \le n-1$, separated by single spaces, where $n$ is the numbers of nodes in the graph, $m$ is the number of edges, $s$ is the source and $t$ is the sink ($s \ne t$). Nodes are numbered from $0$ to $n-1$. Then follow $m$ lines, each line consisting of four (space-separated) integers $u$, $v$, $c$ and $w$ indicating that there is an edge from $u$ to $v$ in the graph with capacity $1 \le c \le 10\, 000$ and cost $1 \le w \le 1\, 000$.

Output

Output a single line containing two integers; the size $F$ of a maximum flow from node $s$ to node $t$, and the cost of a mimimum cost flow of size $F$. You may assume that $F < 2^{31}$.

Sample Input 1 Sample Output 1
4 4 0 3
0 1 4 10
1 2 2 10
0 2 4 30
2 3 4 10
4 140
Sample Input 2 Sample Output 2
2 1 0 1
0 1 1000 100
1000 100000
Sample Input 3 Sample Output 3
2 1 1 0
0 1 1000 100
0 0

Please log in to submit a solution to this problem

Log in