AtCoder Beginner Contest 236 G 問題 Good Vertices

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

有向グラフ $D=(V=[\![N]\!], A=\{u_1 v_1, \dots, u_T v_T \})$ が与えられる. 部分有向グラフ $D_1, \dots, D_T$ を $D_t=(V, A_t)$ として,

$A_t=\{u_1 v_1, \dots, u_i v_i\}$

とする. $w=1,2,\dots, N$ に対して, 次を満たすような $t$ は存在するか? 存在するならば最小値を求めよ.

$D_t$ において, 頂点 $1$ から $w$ へちょうど $L$ 本の有向辺をたどって移動できる.

制約

$2 \leq N \leq 100$
$1 \leq T \leq N^2$
$1 \leq L \leq 10^9$
$D$ に多重辺は存在しない.

解法1 (問題の言い換え)

結局は以下の問題を解くことになる.

有向グラフ $D$ において, 頂点 $1$ から頂点 $w$ への有向歩道のうち, 使う辺の本数がちょうど $L$ であるものは存在するか? 存在するならば, このような有向歩道において使用する辺の重み最大値として可能な最小値を求めよ.

解法2 (動的計画法の導出)

動的計画法で解くことを考える. ${\rm DP}[i,j,l]$ で頂点 $i$ から頂点 $j$ へちょうど $l$ 本の有向辺からなる有向歩道における利用する辺の最大値の最小値とする. ベースケースと更新式は,

${\rm DP}[i,j,0 ]=\begin{cases} 0 & (i=j) \\ \infty & (i \neq j) \end{cases}$

$\displaystyle {\rm DP}[i,j,l ]=\min_{k \in V} \max({\rm DP}[i,k,l-1], \operatorname{cost}(k,j))$

となる. ただし, $x,y in V$ に対して,

$\operatorname{cost}(u,v)=\begin{cases} t & (xy \in A, xy=u_t v_t) \\ \infty & (xy \not \in A) \end{cases}$

する.

解法3 (行列累乗での高速化)

更新式において, 2つの演算 $\oplus, \otimes$ をそれぞれ $\min, \max$ に対応させると, 更新式は

$\displaystyle {\rm DP}[i,j,l ]=\bigoplus_{k \in V} ({\rm DP}[i,k,l-1] \otimes \operatorname{cost}(k,j))$

ここで, この更新式を観察してみると, 以下の式と類似していることがわかる.

$n$ 次正方行列 $A=(a_{i,j}), B=(b_{i,j}), C=(c_{i,j})$ において, $C=AB$ であるとき, $\displaystyle c_{i,j}=\sum_{k=1}^n a_{i,k} b_{k,j}$ である.

このことを念頭に入れる. 代数系 $R=(\mathbb{N} \cup \{\infty\}, \oplus, \otimes)$ は $\oplus$ の単位元を $\infty$ , $\otimes$ の単位元を $0$ に持つ擬環になる. この擬環において, $C=(\operatorname{cost}(i,j))$ とすると, $C^L$ の第 $(i,j)$ 成分は ${\rm DP}[i,j,l]$ に一致する.