この記事は 帰ってきた AOJ-ICPC Advent Calendar 2022 4日目 の記事です。
https://onlinejudge.u-aizu.ac.jp/challenges/search/titles/2571 (800点)
問題概要
個の島があり、最初は全て孤立している。
島 と島 の間に橋をかけるコストが のとき、全体を連結にするためのコストの総和の最小値を求めよ。
ただし、島 にかかっている橋の本数は 以下という制限がある。
制約
解法
でソートしておく。
ならば
もし全てならば が達成できる。
となる島があった場合が厄介でそれを考える。
となる を順に , となる を順に とする。
連結にするためには, に含まれる島は に含まれる島とつなぐ必要があり, 個の連結成分が残る。
残った 個の連結成分は, とつなぐのが最適である。
に含まれる島と に含まれる島の最適なつなぎ方は二部マッチングを考えると
- 流量 , コスト の の辺
- 流量 , コスト の の辺
- 流量 , コスト の の辺
を張った 頂点のグラフで の 流量 の最小費用流を求めれば計算できる。
が、ACLを使うと でTLEしてしまう。
ここでコスト関数の構造を利用すると、
- 流量 , コスト の の辺
- 流量 , コスト の の辺
- 流量 , コスト の の辺
- 流量 , コスト の の辺
を張った 頂点のグラフで の 流量 の最小費用流を求めることでも計算できるため、ACLを使うと に改善することができ、ACすることができる。
が、7.47s (TL 8s) なので何かがおかしく、実際にこれよりオーダーがいい解法が存在しました。( 公式解説 )
となるような について島 と島 , 島 と島 がつながる場合が最適になることはない(交差することはない)ため、島 を 個に倍化することで適当に dp ができます。
島 がつながる先は が小さいところから前後 個を見ておけばいいのでこの dp は に改善することができます。
あとがき
飛ばしてたけど模擬地区Cをやったあとに見たらすぐに解けた & 最小費用流解法が見当たらなかったので書きました。
TLギリギリなので他に見当たらないのはACL最強というだけなのかもしれない、