2017-08-08から1日間の記事一覧

POJ 3155: Hard Life

http://poj.org/problem?id=3155良問だと思う。hardness factorがkの時実現可能か考える。 辺と点を対応させた二部グラフを作る。 辺からそれが含む点に対して辺をはる。 そして辺にコスト1,点にコスト-kをつけると、Maximum Closure Problemに帰着できるの…