# Network Flow - Minimum Cost Flow

Time Limit : 1 sec, Memory Limit : 65536 KB

# ŏp

eӂɃRXgݒ肳ꂽt[lbg[NɂāAn_ $s$ I_ $t$ ܂ŗp $F$ ̃t[𗬂߂̍ŏRXg߂ĂB

t[lbg[N̊e $e$ ɂ͗e $c(e)$ yуRXg $d(e)$ ݒ肳Ă܂Be $e$ ɂ͗e $c(e)$ 𒴂Ȃ $f(e)$ ̃t[𗬂Ƃł܂Bn_ $s$ I_ $t$ ֗ $F$ ̃t[𗬂Ƃ́A$\sum_{e} (f(e) \times d(e))$ ̍ŏl߂ĂB

t[lbg[N $G(V,E)$ ȉ̌ŗ^B

$|V|\;|E|\;F$
$u_0\;v_0\;c_0\;d_0$
$u_1\;v_1\;c_1\;d_1$
:
$u_{|E|1}\;v_{|E|-1}\;c_{|E|-1}\;d_{|E|-1}$

$|V|$, $|E|$, $F$ ͂ꂼt[lbg[N $G$ ̒_̐Aӂ̐AʂB $G$ ̒_ɂ͂ꂼ $0, 1, ..., |V|-1$ ̔ԍtĂAn_ 0AI_ $|V|-1$ ƂB

$u_i$, $v_i$, $c_i$, $d_i$ ̓t[lbg[N $G$ $i$ Ԗڂ̕ӂ\A_ $u_i$ 璸_ $v_i$ Ɍėeʂ $c_i$ ŃRXg $d_i$ ̕ӂ邱Ƃ\B

## o

ŏpPsɏo͂BAn_ $s$ I_ $t$ ֗ $F$ ̃t[𗬂ƂłȂꍇ -1 Psɏo͂B

• 2 ≤ $|V|$ ≤ 100
• 1 ≤ $|E|$ ≤ 1000
• 0 ≤ $F$ ≤ 1000
• 0 ≤ $c_i$, $d_i$ ≤ 1000
• $u_i$ $\ne$ $v_i$
• _ $x$ 璸_ $y$ ɌĕӂꍇA_ $y$ 璸_ $x$ ɌӁitӁj͂ȂB

## ͗

4 5 2
0 1 2 1
0 2 1 2
1 2 1 1
1 3 1 3
2 3 2 1


## o͗

6
`