読者です 読者をやめる 読者になる 読者になる

【グラフ理論とネットワーク理論】Network and Flow #3

Introduction Here is the article I wrote last time class. keita-matsushita.hatenablog.com Network and Flow Network is defined as below. ・Network : Graph G(V, E) in which branch capacity Ci(> 0) is defined. ・f(vi, vj) : Branch flow value …

【グラフ理論とネットワーク理論】Matrix Expression of Graphs and Paths #2

Introduction Here is the article of the last time class. keita-matsushita.hatenablog.com Matrix Expression of Graphs and Paths Graphs can be expressed by matrixes. Below matrixes express above the graph. Incidence matrix (接続行列) Cols re…

【グラフ理論とネットワーク理論】Graph #1

グラフとは何か グラフは以下のコンポーネントで成り立つ。 節点、頂点: 対象物(スイッチ、ルータ) Node, Vertex: Objectives(Switch, Router) 枝、辺: 接点間の関係(伝送路) Branch, Edge: Relation among nodes(Transmission lines) つまり、グラフとは節…

ツリーグラフにおける最短ルートの算出

問題 B: ツリーグラフ - AtCoder Regular Contest 030 | AtCoder 解法 与えられたノードからスタートし、宝石を全て取得するように巡回し始めのノードに戻ってくるルートの最短距離を求める問題。 それぞれのノードについて、巡回すべきノードであるか否かを…

GCDGraph TopCoder グラフに置ける2点間に経路があるか否か

問題URL arena.topcoder.com Problem Statement You are given four s: n, k, x, and y. The s n and k describe a simple undirected graph. The graph has n nodes, numbered 1 through n. Two distinct vertices i and j are connected by an edge if and…

トポロジカルソートの組合せを数え上げる

問題 D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder 与えられたDAGをトポロジカルソートしてできる列の通り数を数え上げる問題。普通にトポロジカルソートすると1つの列しか作成されない。 また、全列挙(全てのノードの順列をだし、全ての有効辺を満…

有向非巡回グラフ(DAG)をトポロジカルソートする

有向非巡回グラフ(DAG)とは DAGとは、有向グラフ且つ閉路のないグラフのことである。これは、ある操作の手順を表す時に用いられたりする。DAGはトポロジカルソートをすることができる。 トポロジカルソートとは トポロジカルソートとは、グラフの有向辺の情…

最小全域木の重みの総和を求める

最小全域木とは 最小全域木とは、グラフの全域の中で辺の重みの総和が最小のもの木のこと。つまり、与えられたグラフの全てのノードを含む木を作成する際に、辺の重みが最小になるように作ったものになる。この木を作成するためにプリムのアルゴリズムを用い…

プライオリティキューを用いたダイクストラ法 ~トレジャーハント編 ~

問題 D: トレジャーハント - AtCoder Beginner Contest 035 | AtCoder 解法 流れ 滞在する必要のある頂点は1つと考える。滞在する頂点を頂点iとすると、頂点0から最短で頂点iに到達し、できるだけ長く頂点iに滞在し、最短で頂点0に戻る事を考える。頂点iを…

bit操作と深さ優先探索の全列挙を比較する

問題 http://abc045.contest.atcoder.jp/tasks/arc061_a 解き方 全列挙できるか 全ての数字と数字の間に対して、「+」を入れる場合と入れない場合で全列挙。文字列の長さがNの場合、「+」を入れることができる箇所は全部で(N - 1)個。それぞれの箇所に「+」…

動的計画法を使うことでアスレチックで遊ぶ時に体力の消耗を抑える

問題 C: 柱柱柱柱柱 - AtCoder Beginner Contest 040 | AtCoder 解き方 全探索では計算量がO(2n)となり間に合わない。よって動的計画法を用いて解く。 なぜ動的計画法が使えるか 部分問題を解き、その計算結果を保存し再利用することで全体の問題が解ける。i…

深さ優先探索を用いて社長のお給料を決める

問題 C: 高橋君の給料 - AtCoder Beginner Contest 026 | AtCoder 解き方 問題の入力値から、上司と部下の関係をグラフを起こす。すると、今回の問題では部下に対する上司の人数は必ず1人なので木構造になる。 根ノードは社長になり、葉ノードは部下を持た…

ワーシャル・フロイド法を使って全点間の最短距離を算出する(グラフ理論)

問題 C: Blue Bird - AtCoder Beginner Contest 022 | AtCoder ソースコード 解説 AtCoder Beginner Contest 022 解説 ダイクストラ法で解けそうであるが、頂点Aから、どこかにいき再び頂点Aに戻ってくる経路は閉路なためそのままではダイクストラ法やワーシ…