Kazun の競プロ記録

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

AtCoder Beginner Contest 243 E問題 Edge Deletion

AtCoder ABC ABC243 E問題 500 pts

問題

提出解答

問題の概要

重みつき連結無向グラフ $G=(V:=[\![N]\!], E=\{A_j B_j \mid j=1,2, \dots, \}, W)$ が与えられる. ただし, $W(A_i B_j)=C_j$ である. このとき, 以下を満たす $E$ の部分集合 $F$ のサイズの最大値を求めよ.

$G-F$ は連結.
$\forall u,v \in V, \operatorname{dist}_G(u,v)=\operatorname{dist}_{G-F}(u,v)$

ただし, 連結グラフ $H=(V(H), E(H))$ と $u,v \in V(H)$ に対して, $\operatorname{dist}_H(u,v)$ で $u,v$ 間の距離とする.

制約

$1 \leq N \leq 300$
$1 \leq M \leq \frac{1}{2}M(M-1)$
$1 \leq A_j \lt B_j \leq N$
$1 \leq C_j \leq 10^9$
$G$ は単純無向連結グラフ

解法

結論から言うと, $F$ として,

$F=\{ab \in E \mid \exists c \in V ~{\rm s.t.}~ c \neq a,b, \operatorname{dist}_G(a,b)=\operatorname{dist}_G(a,c)+\operatorname{dist}_G(c,b)\}$

とすればよい. この $F$ において, $|F|$ が答えになる.

証明は以下の公式解答を参考にすること

$\operatorname{dist}_G(\bullet, \bullet)$ を求める方法について, Warshall-Floyd 法を利用することにより, 全点間距離を $O(N^3)$ で求めることができ, $F$ も $O(MN)$ で構成できる.