beet's soil

競プロのことなど

AOJ 2872 Ebi-chan Lengthens Shortest Paths

双対パンチ👊

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

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


元のs-t最短路の長さを  len とし、 辺  e  b_e だけ伸ばすことにすると、
 \min_{b,p}{\sum_{e}{c_e b_e}}
s.t.
 p_v - p_u \le w_e + b_e
 p_t - p_s \ge len + 1
となります

最小費用流の双対の形になるように変形すると(目的関数を-1倍していることに注意)
 \max_{b,p} {- \sum_{e}{c_e b_e} - \infty \times b_{ts} }
s.t.
 -b_e + p_v - p_u \le w_e
 -b_{ts} + p_s - p_t \le -(len + 1)
となります

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