いろいろがんばりたいブログ

情報科学科の人がいろいろ書きます。

2013-10-22から1日間の記事一覧

POJ 1637 Sightseeing tour

オイラー閉路にtwo-wayなエッジを追加した問題. 最大流で解けます。考え方は以下の通り まずtwo-wayなエッジであろうと入力そのまま有向なエッジとしてグラフに追加していく。 出るエッジについて-1,入るエッジについて+1を各ノードで計算しておく。通常のオ…