ARC107F

https://gyazo.com/6e9ee2b88a1436d182987795574d233d

https://gyazo.com/4357c3c678c3b421398f123b3af31067

考えたこと

最小カット絡みであることは既知

頂点を削除して、連結成分に分ける

連結成分のBの和の絶対値がスコアになる

うーん、連結成分をどう表現するのかさっぱりわからない

なるほど、わかった

一旦寝て明日見ないで考察しよう

$ \left|\sum x_i\right| = \max\left(\sum x_i, \sum -x_i\right)

これで絶対値が最大化問題に置き換わる

頂点を削除してスコアの最大化をするところと、スコアの計算自体の最大化とがあるので一旦分けて考える、つまりグラフは与えられて編集しないとする

この時「プラスかマイナスかを選ぶ二択」なので二色塗り分けであり、カットになる

連結成分の中では同じものを選ばなければならない

これは「もし二頂点u,vが隣接するなら、その二つの頂点の色は同じでなければならない」と変換できる

これは互いにINFの辺を引くことで表現できる

スコアは最大化したい。なので最大のスコアと比べた損失を辺の重みにして最小カットにする

素直に書くと負の辺がある(上の図)

十分大きな数N(ここでは10)をすべての辺に足したのが下図

最小カットは19で、2N-19が求める値になる

https://gyazo.com/ca0017a873fa8ec8ad5c0a990e852096

https://gyazo.com/989ed2c781670342f21534d359643a8c

さて、ここまでで頂点が固定されてる時のスコアの計算はできた

次は頂点が削除される時だ

頂点を削除するしないの二択と正か負かの二択の二つがある

素朴にくっつけるとこうなる

https://gyazo.com/c4369c6922fc0ef20ece52dcfad65821

だけどこれではうまくいかない

Sの右の辺がコスト0ならそこで切るのが最小になってしまう

ここにも同様に10を乗せる？

3の頂点を消してるのに無限大辺の制約が生きてる(図で見落としてる)

「消さない」であって、かつ「負」の時にのみ「隣が負でなければ無限大ペナルティ」となるべき

まず「二つの二択の組み合わせ」についてもっと掘り下げる

今回「消す消さない」「正か負か」の2つの二択があるが、消す時には正か負か関係ない

うーん、でもそれだと「消されてる時には負に塗られててもペナルティなし」みたいな表現が必要になるな…

公式解説

なるほど、2つの頂点それぞれの塗りと2つの二択は対応しないで良いわけだ

https://gyazo.com/3d2a89d040886e82cbf3f92b2903ae3d

2つの選択肢をそれぞれ頂点の塗りに対応させようとしない(論理積とかやりにくいので)

かわりに掛け合わせの4通りに配置する

TSはBAに無限大辺を引くことで消せる

残りの3つのうち、TTの時だけAはT、SSの時だけBはS

無限大辺は「根元がSのとき先がTではいけない」という制約。

これで「ある頂点が正の時、隣は負ではいけない」を表現する(正負は交換してもここでは関係ない)

なのでSSとTTを正と負に割り当てることに決まる(どちらがどちらでも良い)

https://gyazo.com/1e35dad9482f692232a562bb5f85ea26

最小カットなので3が正の時3得られることを-3とする、よくなる方向が小さい

辺が負になることをまずは気にしないで方向を合わせるのが混乱しないと思う

次に負の辺を無くすために適当にオフセットする

https://gyazo.com/039cd4cd0142e78ff0cf8da6af4b884f

各辺を10増やした

最小カット

https://gyazo.com/6e9ee2b88a1436d182987795574d233d

これはつまり3を消して-4を4にする選択

10×2-16で4になる