University of Aizu Programming Contest 2014 (AOJ 1548) Yu-kun Likes a Directed Graph

お題箱より。

解法

重み $w$ の負辺を足してできるだけ重み合計が大きい（ $0$ に近い）負閉路を作りたいので、与えられたDAGについて「1本以上の辺で構成されるパスであって、重み合計が $|w|$ 未満であるもののうち一番大きいものの重み」が分かれば良いです。

ここで $|w| \le 100$ であること、さらに元々のDAGにある辺の重みは非負であることに注目します。これらの条件から、最終的に見つけるパスも、その一部となるパスも、重みが $100$ 以下のものだけを考えれば良いことが分かります。

よって以下のようなDPテーブルを構成し、 $0 \le s \le 100$ の範囲で計算していけば良いです。

$dp\lbrack i \rbrack\lbrack s \rbrack$ ：1本以上の辺で構成され、頂点 $i$ で終わるパスであって、重み合計が $s$ となるものが存在するか？（true/false）

トポロジカル順序に基づいて順番に計算していきます。遷移は頂点 $i$ から頂点 $j$ への重み $c$ の辺が存在する時に、

$i$ から始まり $j$ で終わるパス： $dp\lbrack j \rbrack\lbrack c \rbrack$ をtrueにする
$i$ 以外から始まり $j$ で終わるパス： $dp\lbrack i \rbrack\lbrack s \rbrack$ がtrueである $s$ について、 $dp\lbrack j \rbrack\lbrack s+c \rbrack$ をtrueにする