AOJ 2345 : Network Reliability

AOJ 動的計画法グラフ数学

無向グラフ $G = (V, E)$ と整数 $p$ が与えられる． $G$ の各枝が独立に $p$ パーセントの確率で消失するとき，グラフが連結である確率を求めよ．

AOJ 1178: A Broken Door

日本語なので略。

$\mathbb{Z}^3$ に半順序関係 $\prec$ を

$(x_1, y_1, z_1) \prec (x_2, y_2, z_2) \overset{\triangle{}}{\Leftrightarrow} x_1 < x_2$ かつ $y_1 < y_2$ かつ $z_1 < z_2$

で導入する。 $n$ 個の $\mathbb{Z}^3$ の点の中で、上記で定めた半順序を満たす最長の列の長さを求めよ。