あああああ

オタク & 競プロ

Floating Islands (AOJ 2571)

この記事は 帰ってきた AOJ-ICPC Advent Calendar 2022 4日目 の記事です。

https://onlinejudge.u-aizu.ac.jp/challenges/search/titles/2571 (800点)

問題概要

 n 個の島があり、最初は全て孤立している。

 i と島 j の間に橋をかけるコストが  |p_i - p_j| のとき、全体を連結にするためのコストの総和の最小値を求めよ。

ただし、島 i にかかっている橋の本数は  d_i 以下という制限がある。

制約

 2 \le n \le 4000

 1 \le p_i \le 10^9

 1 \le d_i \le n

解法

p_i でソートしておく。

 \sum d_i \lt 2(n-1) ならば -1

もし全て d_i \ge 2ならば p_n - p_1 が達成できる。

 d_i = 1 となる島があった場合が厄介でそれを考える。

 d_i = 1 となる  i を順に a_1, \dots, a_x , d_i \gt 1 となる  i を順に b_1, \dots, b_y とする。

連結にするためには,  a に含まれる島は  b に含まれる島とつなぐ必要があり, y 個の連結成分が残る。

残った y 個の連結成分は,  (b_1,b_2), (b_2,b_3), \dots , (b_{y-1},b_y) とつなぐのが最適である。

 

 a に含まれる島と  b に含まれる島の最適なつなぎ方は二部マッチングを考えると

  • 流量 1 , コスト 0 s \to a_i の辺
  • 流量 1 , コスト  |p_{b_j} - p_{a_i}|  a_i \to n + b_j の辺
  • 流量 d_{b_j} - 1 , コスト 0 n + b_j \to t の辺

を張った 2n + 2 頂点のグラフで  s \to t の 流量 x の最小費用流を求めれば計算できる。

が、ACLを使うと O(n^3logn) でTLEしてしまう。

 

ここでコスト関数の構造を利用すると、

  • 流量 1 , コスト 0 s \to a_i の辺
  • 流量 d_{b_j} - 1 , コスト 0 b_j \to t の辺
  • 流量 \infty , コスト  p_{i+1} - p_i  i \to i+1 の辺
  • 流量 \infty , コスト  p_{i+1} - p_i  i+1 \to i の辺

を張った n + 2 頂点のグラフで  s \to t の 流量 x の最小費用流を求めることでも計算できるため、ACLを使うとO(n^2logn) に改善することができ、ACすることができる。

実装例

 

 

 

 

が、7.47s (TL 8s) なので何かがおかしく、実際にこれよりオーダーがいい解法が存在しました。( 公式解説 )

 

 i \lt j , k \gt l となるような  i,j,k,l について島  a_i と島 b_k , 島 a_j と島 b_l がつながる場合が最適になることはない(交差することはない)ため、島 b_j  d_{b_j} - 1 個に倍化することで適当に O(n^3) dp ができます。

a_i がつながる先は  | p_{b_j} - p_{a_i} | が小さいところから前後  \pm n 個を見ておけばいいのでこの dp は O(n^2) に改善することができます。

 

あとがき

飛ばしてたけど模擬地区Cをやったあとに見たらすぐに解けた & 最小費用流解法が見当たらなかったので書きました。

TLギリギリなので他に見当たらないのはACL最強というだけなのかもしれない、