srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

グラフ

SRM 693 div2 easy TriangleEasy

問題 問題概要 グラフが与えられる。そのグラフの中に三角形を作る。最小でいくつの辺を加えればできるか。 解法 まず、辺が1つもなければ、必要な最小の辺の数は3となる。次に辺がある場合を考える。u - v の辺がある場合を考える。このとき、u - x(xはvで…

codeforces 368 div2 B. Bakery

問題 問題概要 小麦屋さん以外の頂点でパン屋を開こうとする場合に、もっとも小麦屋さんから近くでパン屋を開ける頂点までの距離をもとめよ。開けないなら-1。 解法 ダイクストラで解いた。スタートをすべての小麦屋さんにして、それらの頂点からほかの頂点…

ARC 022 C - ロミオとジュリエット

問題 問題概要 木の直径を求める。 解法 木の直径を求めるアルゴリズム。 適当な頂点から最も遠い頂点xを選び、さらに、xから最も遠い頂点yを選ぶ。xとyの距離が木の直径となる。 ミス 直径は初めて。 コード #include <iostream> #include <algorithm> #include <vector> #include <queue> #incl</queue></vector></algorithm></iostream>…

aoj 0562 - Shopping in JOI Kingdom

問題 問題概要 複数のスタート場所があり、地点までの最短距離を求める。 解法 まず、ダイクストラを利用して、店から他の地点までの最短距離を入れる。このときの店というのは複数ある場合があるので、一番近い店からの距離を求めなければならない。最短距…

yukicoder No.241 出席番号(1)

問題 問題概要 省略。 解法 tmpに0からn-1まで入れて、それらを条件を満たすまで、シャッフルし続ける感じで解いた。WAだろうなと思ってひとまず書いてみたが、通った。条件を満たす場合が多いらしい。 2部マッチとかで解けるみたいなので解きます。 ミス …

aoj 0519 - Worst Reporter

問題 問題概要 試合結果が渡されて、順位がどのように決まるかを求める問題。 解法 まず、試合結果がわからないものは無視して、与えられた試合結果のみを使い、トポロジカルソートをする。aチームが勝ち、bチームが負けた場合、b -> aのような形で辺を貼る…

aoj 0596 - Taxis

問題 問題概要 与えられたグラフに対して、幅優先探索を使い、条件を満たした新たなグラフを表す隣接行列を作り、ダイクストラで最小コストを作る。 解法 与えられたグラフのままでは、多くの条件あり、そのままではダイクストラをすることができない。そこ…

yukicoder No.19 ステージの選択

問題 問題概要 強連結成分の分解を利用する問題。強連結成分を1つの頂点に置き換えて、DAGにして、トポロジカルソートをする。 解法 N個のステージを頂点と考える。(先に指定しておくと良いステージ) -> (ステージ)の向きに有向辺をはっていき、有向グラフ…

aoj GRL_3 Connected Components - Strongly Connected Components

問題 問題概要 強連結成分分解する問題。 解法 強連結成分を分解するアルゴリズムとして、Kosarajuというものがある。今回はそれを使って、実装した。アルゴリズム自体は下のサイトを見てもらえれば、分かりやすい。 mathtrain.jp ミス アルゴリズム自体の理…

yukicoder No.17 2つの地点に泊まりたい

問題 問題概要 省略 解法 まず、任意の2点間の距離の最小値を求めておく。その後、滞在する2点を全探索で全て調べる。 全探索で dist[0][i] + dist[i][j] + dist[j][n - 1] + s[i] + s[j] の最小値を求めればいい。 ミス 特になし。 コード #include <iostream> #inc</iostream>…

yukicoder No.392 2分木をたどれ

問題 問題概要 完全2分木上をどのようにたどれば、ルートから指定された場所に移動できるかを求める問題。 解法 完全2分木問題は1オリジンにで考えると、配列を使い親と左子、右子を簡単にたどれる。 今回はそこまで考える必要はない。単に奇数なのか偶数…

aoj 0526 - Boat Travel

問題 問題概要 連続したクエリの中に頂点とそれをつなぐ辺の長さのクエリと、2点間の最短距離を求めよというクエリが含まれる。 解法 任意の2点間の距離を求めるにはワーシャルフロイト法で求めることができる。ただし、最短経路を求めよというクエリに対し…

AOJ 2382 - King Slime

unionfind tree構造を用いる問題