Asteroids (PKU 3041)

http://mirac.jp:8080/cgi-bin/pku_prob.cgi?nosub=1&id=3041

解法

NxNの宇宙空間に小惑星がK個ある。行または列にある全ての小惑星を蒸発させることのできる強力な兵器があり、その兵器を用いて小惑星を全て破壊したい。最低何回兵器を使わなければならないか？
1<=N<=500
1<=K<=10000

問題

XのN個ノードとYのN個ノードがあり、小惑星がある位置を辺とした2部グラフ上で最大流を流す。