8615: GRL_6_B : Minimum Cost Flow
Description
Find the minimum cost to send a certain amount of flow through a flow network.
The flow network is a directed graph where each edge $e$ has capacity $c(e)$ and cost $d(e)$. Each edge $e$ can send an amount of flow $f(e)$ where $f(e)≤c(e)$.
Find the minimum value of $\sum_e (f(e)×d(e))$ to send an amount of flow $F$ from source $s$ to sink $t$.
Input
The first line contains three numbers, |V|, |E|, F are the number of vertices, the number of edges, and the amount of flow of the flow network respectively. The vertices in G are named with the numbers 0,1,...,|V|−1. The source is 0 and the sink is |V|−1|.
The following |E| lines contain four numbers, $u_i, v_i, c_i, d_i$ represent i-th edge of the flow network. A pair of $u_i$ and $v_i$ denotes that there is an edge from $u_i$ to $v_i$, and $c_i$ and $d_i$ are the capacity and the cost of i-th edge respectively.
Output
Constraints
$1 ≤ |E| ≤ 1000$
$0 ≤ F ≤ 1000$
$0 ≤ c_i, d_i ≤ 1000$
$u_i ≠ v_i$
If there is an edge from vertex x to vertex y, there is no edge from vertex y to vertex x.
Sample 1 Input
4 5 2
0 1 2 1
0 2 1 2
1 2 1 1
1 3 1 3
2 3 2 1
Sample 1 Output
6