keyword Dijkstra C++ 概要 有向グラフが与えられる。ある目的地に行って戻ってくる(最短経路を使って)までの合計時間が最大になるものをみつけ、その合計時間を求める問題。ノード数は1000以下。 ダイクストラするだけ。帰りは辺を逆に張ればよい。

keyword 2部マッチング C++ 概要 P( 生徒と委員会を2部グラフに見立てて2部マッチングの最大個数が委員会の数と一致するか見れば良い。

keyword 最大流 C++ 概要 最大流の問題。 ソース略。

keyword 探索 C++ 概要 2次元の迷路が与えられる。右手則、左手則でゴールにたどり着くまでの時間と最短の時間を求める問題。 愚直に書くだけ。右手則でゴールにたどり着けることは保証してよいらしい。

keyword 探索 C++ 概要 2次元のボード上に石がいくつかある。この上でカーリングをして滑るヤツを目的地に持っていきたい。滑るヤツは石に当たるまで止まらないし、石に当たるとぶつかった石を破壊する。最短で何回滑らせれば良いか求める問題。ただし10回以…

keyword Dijkstra C++ 概要 2次元平面上に、現在地と目的地と、電車の路線図が与えられる。電車と徒歩の速度は一定の値をとる。電車を自由に使ってよいとき、目的地までの移動にかかる最小の時間を求める問題。 ダイクストラの練習問題。