Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 256 E問題 Takahashi's Anguish

AtCoder ABC ABC256 E問題 500 pts

問題

提出解答

問題の概要

$X_1, \dots, X_N$ は全て $X_i \neq i$ である $1$ 以上 $N$ 以下の整数である.

$(1,2, \dots, N)$ の並び替え $P$ に対する $i$ 番目の不満度を以下のようにして定義する.

整数 $s,t$ は $P_s=i, P_t=X_i$ であるとする. このとき, $s \gt t$ ならば, $i$ 番目の不満度は $C_i$ , そうでなければ $i$ 番目の不満度は $0$ .

全ての $(1,2, \dots, N)$ の並び替えにおける $1$ 番目から不満度 $N$ 番目の不満度の総和を見たとき, 不満度の総和の最小値を求めよ.

制約

$2 \leq N \leq 2 \times 10^5$
$1 \leq X_i \leq N$
$X_i \leq i$
$1 \leq C_i \leq 10^9$

解法

次のような有向グラフ $D=(V,A)$ を考える.

$V:=\{1,2, \dots, N \}, \quad A:=\{\overrightarrow{i X_i} \mid i=1,2, \dots, N \}$

この有向グラフは $V$ から $V$ への写像と1対1に対応することから Functional Graph と言われている.

この Functional Graph には次のような性質がある.

Functional Graph の各弱連結成分 *1 にはちょうど1つの有向サイクルがある.

弱連結成分の頂点のうち, サイクルをなす頂点を順に $v_1, \dots, v_k$ , 残りの頂点を $w_1, \dots, w_r$ とする. このとき, 問題は頂点を順に塗っていくとき, それぞれの辺について終点よりも先に始点を塗ってしまった辺における不満度がたまるとみなされる. よって, サイクルの辺のうち, 少なくとも1つの辺については見捨てなくてはならない. そして, サイクルの辺のうち, 不満度が最小であるような辺のみを見捨てるような辺の塗り方の順番が存在する.

以上から, 不満度の和の最小値は Functional Graph の各サイクルを構成する不満度の最小値の総和である.

Functional Graph におけるサイクルの検出は Union Find を利用することにより, $O(N \alpha (N))$ で計算できる.

*1:有向グラフの全ての辺を無向辺とみなしたときの連結成分