AOJ 2872 Ebi-chan Lengthens Shortest Paths

双対パンチ👊

グラフの辺を伸ばすので、これは双対ゲーです。

双対についてはこちら↓
beet-aizu.hatenablog.com

元のs-t最短路の長さを len$len$ とし、 辺 e$e$ を be$b_e$ だけ伸ばすことにすると、
minb,p∑ecebe$\underset{b,p}{min}\sum _e{c}_e{b}_e$
s.t.
pv−pu≤we+be$p_v-p_u\le w_e+b_e$
pt−ps≥len+1$p_t-p_s\ge len+1$
となります

最小費用流の双対の形になるように変形すると（目的関数を-1倍していることに注意）
maxb,p−∑ecebe−∞×bts$\underset{b,p}{max}-\sum _e{c}_e{b}_e-\mathrm{\infty }\times b_{ts}$
s.t.
−be+pv−pu≤we$-b_e+p_v-p_u\le w_e$
−bts+ps−pt≤−(len+1)$-b_{ts}+p_s-p_t\le -(len+1)$
となります

あとは負辺ありの最小循環費用流を流して終わりです。
辺は u$u$-> v$v$ に流量 cuv$c_{uv}$、コスト duv$d_{uv}$ を、
t$t$-> s$s$ に流量 ∞$\mathrm{\infty }$、コスト −(len+1)$-(len+1)$ を貼ればいいです。

提出

judge.u-aizu.ac.jp