2/6 PKU

3204 Ikki's Story I - Road Reconstruction

N個の街とそれらを結ぶM本の一方通行の道がある。それぞれの道には容量が決まっている。街0から街N-1まで移動する容量を考え、道を再建したときに容量が増加するような道は何本あるか。

最大流で解を求めた後、残余グラフを考え、街0から街N-1までの経路を発生させるような辺を求める