線形構成法 Linear Design Method 直径最小化問題 Minimizing Diameter Problem (n, d) グラフとは、接点数n, 各接点は出枝、入枝をそれぞれd本ずつもっているグラフのこと。このグラフの事をd正則有向グフラと呼ぶ。 また、経路の長さは、経路中の枝の数で…

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 …

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…

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

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

問題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をトポロジカルソートしてできる列の通り数を数え上げる問題。普通にトポロジカルソートすると１つの列しか作成されない。 また、全列挙(全てのノードの順列をだし、全ての有効辺を満…

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

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

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

問題 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 解き方 問題の入力値から、上司と部下の関係をグラフを起こす。すると、今回の問題では部下に対する上司の人数は必ず１人なので木構造になる。 根ノードは社長になり、葉ノードは部下を持た…

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