dwangoプログラミングコンテスト D - タクシー

• 問題
• AC

最小費用流なので、とりあえずグラフを二周くらいしながら需要と供給を解消していって、循環流になおす。あとは負閉路を解消すれば最適になるが、このグラフ上の負閉路は環状線を一周するものしかありえないので、ここにできるだけ流せばよい。具体的には、残余グラフ上の負辺を集めて$(上限流量、辺の重み)$を上限流量の昇順でソートして、先頭から順に（一周のコストが負である限り）上限流量いっぱいに流すことを繰り返した。