問題（外部リンク） 3126 -- Prime Path 実装の概要 それぞれの素数をグラフの頂点と考え、ある特定の桁だけ数字を変えれば良い場合は距離を1として初期化します。 その後はある頂点から別の頂点までの最短距離を求める問題と考えることができます。ワーシャ…

問題（外部リンク） 2395 -- Out of Hay 実装の概要 最終的に構成したいのは最小全域木ですが、今回は距離の総和ではなく全域木を構成する辺の中で最長のものの長さです。 そのため、クラスカル法の一部を変更し最大の距離を保存できるようにすることで解く…

問題（外部リンク） Save your cats | Aizu Online Judge 実装の概要 問題の条件を言い換えると、「与えられたグラフから閉路が無くなるように辺を取り除く場合、取り除いた辺の長さの総和の最小値はいくらか」ということになります。 そのため、クラスカル…

問題（外部リンク） 2377 -- Bad Cowtractors 実装の概要 今回は普段とは異なり「なるべくコストの大きい」全域木を作ることが目標です。 ただ、既にプリム法やクラスカル法を実装したことがあれば条件式を逆にすれば良いので既存のコードを再利用することが…

問題（外部リンク） 1258 -- Agri-Net 実装の概要 グラフ全体での最小コストを求める問題です。今回の実装ではクラスカル法を使いました。 クラスカル法の計算量は頂点数をE, 辺の数をVとするとです。今回は密グラフなので辺の数はそれなりに多いですが十分…

問題（外部リンク） Road Construction | Aizu Online Judge 実装の概要 条件より首都から各都市への距離が最短である必要があるので単一始点最短路問題として解きます。Nの値が大きい割に辺の数はMダイクストラ法であれば十分間に合います。 今回は距離の計…

問題（外部リンク） 3268 -- Silver Cow Party 実装の概要 （2/20 下部に追記あり） パーティー会場xまでの往復距離の最大値を求めたいので、それぞれの地点からxまでの最短距離と、xからそれぞれの地点までの最短距離を求める必要があります。 Nアルゴリズ…

問題（外部リンク） 3259 -- Wormholes 実装の概要 今回の問題ではそれぞれのfieldを行き来するのにpathとwormholeを使うことができ、後者では時間を遡ることができます。 つまり、wormholeの移動コストをマイナスとして扱い、負の閉路（移動距離がマイナス…

問題（外部リンク） 2139 -- Six Degrees of Cowvin Bacon 実装の概要 aとbが共演したことがあれば距離1、aとbは共演してはいないがcはaやbと共演したことがあれば距離2、…というようにab間の距離を定義すれば全点対最短路の問題と考えることができます。 n …

問題（外部リンク） Convenient Location | Aizu Online Judge 実装の概要 ある点から他の点までの最短路を全ての点について行う全点対最短路問題なのでワーシャルフロイド法で解くことができます。かかりますが、町の数が最大でも10なので時間は気にしなく…

だいぶ前に参加したコンテストの問題ですが、しばらく解説を見ても作れないでいたのがようやくACになったので載せておきます。 問題（外部リンク） AtCoder Beginner Contest 065 - AtCoder Beginner Contest 065 | AtCoder 解法の概要 公式の解答にあるよう…