(cache)ACPC_VC_20191209_DIV1

800（大嘘）やめろ

どの町から出発しても、テレポーターを何回か使うことで首都へ辿り着ける　なので、グラフは木
あとは適当にちぎって根にくっつけるんだけど、まあギリギリまで待ったほうがいい気がして実際そう　証明：AC

800（大嘘）やめろ

まあ二つの数列 $A, B$ が存在して $a_{y x} = A_{y} + B_{x}$ なのはそう
二部グラフなので片方の符号を反転すると二変数の差制約になる　→　最小費用流の双対

$A, B$ をポテンシャルと捉えて目的関数が0になるかどうかで判定する

$A_{y} - B_{x} = a_{y x}$ は $A_{y} - B_{x} \leq a_{y x}$ と $A_{y} - B_{x} \geq a_{y x}$ にバラす
条件1は任意の $y, x$ に対して $A_{y} - B_{x} \geq 0$ と書ける

整理すると
$max_{A_{y}, B_{x}} \sum - b$
s.t.
$A_{y} - B_{x} - b_{y x} \leq a_{y x}$
$B_{x} - A_{y} - b_{x y} \leq - a_{y x}$
$B_{x} - A_{y} - b \leq 0$

俺たちのprimaldualを信じろ　→　TLE （それはそう）

グラフとグッと睨むとポテンシャルの差が経路に依存しないことがわかるので、連結成分ごとに適当にやる→AC

構築までするライブラリを持っています　〜完〜
community.topcoder.com

機械的にぶん殴れると、たのしい

beet's soil