赤い辺だけ張ったグラフに最大フローを流したあとの残余グラフを考える。このグラフにできるだけ多くの青い辺を追加しつつ、sourceがsinkにつながらないようにする必要がある。これは青い辺をすべて張ってから最小カットを求めることと同等である。したがって、2回最大フローを流せばよいことになる。
ただ、赤い辺の容量を1にして流すと、入力例3のように赤い辺がボトルネックになって正しい答えが得られない。赤い辺は十分に大きい容量(1000とか)にする必要がある。
バチャ中に適当にやったら通ってしまったのだけど、最後のポイントを納得できていない感じがする。
