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