SRM634Div1Medium
問題
二次平面上のn個の点が与えられる。各点は赤か青に染めることができる。同じ色の点は同じ色の線で結ぶことができ、同じ色の線は交差することができる。違う色の点は線で結ぶことができず、同じ色の
線は交差することができない。ある点同士を赤で結んだ場合のスコアをredScore、青の場合をblueScoreとする。最大のスコアを求めよ。
解法
最大流を用いて解く。
初めに全ての種類の線を引いておき、スコアの総和から最小カットの分だけ値を引く。
ノードは点の組み合わせ、つまり線分を示す。線分の数をN(=)とする。sourceとN個のノードにそれぞれredScore分の容量を持ったエッジを張る。sinkとN個のノードにblueScore分の容量を持ったエッジを張る。
次に、同じ番号のsource側のN個のノードとsink側のN個のノードを十分大きな容量のエッジを張る。これは、2つのノードを同じグループに入れられないようにするためである。
次に交差する線同士にも十分大きな容量のエッジを張る。
これも、前回の処理と同様である。このエッジを張ることで接続されているノードの集合は赤か青のどちらかしか選べないようにしている。
最後に最大流、つまり、最小カットを求めスコアの総和から引く。
Ford-Fulkerson法の場合、計算量はとなる。
なので、Dinic法を使う。
計算量
計算量:
V=
E=
