きままにものづくり

日々の気付いたことなんかを書いてます。

SRM634Div1Medium

問題

二次平面上のn個の点が与えられる。各点は赤か青に染めることができる。同じ色の点は同じ色の線で結ぶことができ、同じ色の線は交差することができる。違う色の点は線で結ぶことができず、同じ色の
線は交差することができない。ある点同士を赤で結んだ場合のスコアをredScore、青の場合をblueScoreとする。最大のスコアを求めよ。

解法

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

計算量

計算量: O(EV^2) = O(n^6)
V=2*n^2+2
E=n^2*n^2

コード

広告を非表示にする