SRM633Div1Medium
問題
ノード数N、エッジ数N-1の2つのツリーが与えられる。各ノードにはスコアを持っている。ノードの集合Sを定義する。S内のノードはツリー1にもツリー2にも含まれている。この時の集合Sのスコアの最大値を求めよ。
解法
任意のノードxを取り出し、そのノードxをルートとする。エッジ数がN-1なので、ループは存在しない。
あるノードyをSに取り入れるためには、その親であるノードzを取り入れる必要がある。これをxに辿り着くまで行う必要がある。スコアが全て正ならノードの数を最大にすれば良いが、スコアには負も含まれるためこの方法は取り入れられない。最小カットを用いてこの問題を解く。求めたいのは最大値なのでスコアの正負を逆転させる。
sourceからxを除く全てのノードに対して容量Mのエッジを張る。スコアの最大値が1000なのでそれが負にならないようにMを設定する。次に、各ノードからM-scoreの容量を持つエッジをsinkに張る。次に、子となるノードから親となるノードに容量が十分大きいエッジを張る。これは、子ノードを使用するためには親ノードが必要であるということを示す。最小カットはU(s,t)が最小となるカットである。sを含むノードの集合がSとなる。子ノードから親ノードに十分大きい容量を持つエッジを張ることで、子ノードをSに含む時は必ず親のノードを含むことになる。子ノードのみを取り入れたとすると、十分大きい容量を持つエッジをカットする必要があるからである。
xを全探索することで答えが求まる。
計算量
Fold-Fulkerson:
F: 最大流
E: エッジ数
全体:
