グラフ理論
解きました 解法 都市の隣接関係のグラフができれば幅優先探索でO(N)で計算できるので、効率よくグラフを構成する方法を考えればいい。 バケット法を使うとうまくいくらしいが二分探索を2d回行うことでもできた。 計算量はO(d N log N) #include <cstdio> #include <vector> </vector></cstdio>…
いまごろですが、通過していました。 西日本のsakataで出場します。 よろしくお願いしますー。 コードと解説をはっておきますコード #include <stdio.h> #include <string.h> #include "sc13.h" #define N 30 #define INF 1000000 int a[N]; int path[N], best, n, path_[N]; in</string.h></stdio.h>…
以前まったく分からなかったが、久しぶりにやってみると解法がすぐ思いついて驚いた。問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0542解法 ある事務所で認証レベルを順番にあげていって、入れる部屋の総数とレベルの表をつくる 最初の…
問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0519解法 トポロジカルソートする。 途中で候補の頂点が複数あらわれた場合、順位表が複数ありえる。 O(V+E)だけど実装下手なせいでO(V^2)になった #include <cstdio> #include <vector> #include <algorithm> using nam</algorithm></vector></cstdio>…
問題 http://poj.org/problem?id=2378 解法 適当な頂点を選んで根にしてDFSして子を数えてやるとできる。 #include <cstdio> #include <algorithm> #include <vector> using namespace std; int N; vector<int> T[10001]; vector<int> ans; int dfs(int p, int q){ int sum = 0; bool f = true; fo</int></int></vector></algorithm></cstdio>…
JOI本選まで一週間を切っています 動的計画法の問題を安定して解けるようになりたい 解法 dijkstra法使う #include <cstdio> #include <algorithm> #include <vector> #include <queue> using namespace std; const int INF = 1 << 29; const int MAX_V = 3000, MAX_E = 100000; typedef pair<int, int> P</int,></queue></vector></algorithm></cstdio>…
解法 二部グラフの最大マッチングとみなせるので最大流問題をとけばいい ford-fulkerson法が使える #include <cstdio> #include <algorithm> #include <vector> using namespace std; const int MAX_N = 200, MAX_M = 200; int N, M; class edge{ public: int to, cap, flow, rev; edge(</vector></algorithm></cstdio>…
問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2005 #include <cstdio> #include <algorithm> using namespace std; const int INF = 1<<29; const int MAX_N = 100; int N,M,S,G0,G1; int cost[MAX_N][MAX_N]; int min_cost[MAX_N][MAX_N]; int wf(){ for(in</algorithm></cstdio>…
問題 解法 最小全域木をつくればいいからプリム法かクラスカル法をつかうといい 僕はプリム法を使いました。 #include <cstdio> #include <queue> #include <vector> #include <algorithm> using namespace std; const int MAX_N = 100; const int INF = 1 << 30; typedef pair<int, int> P; //(cost, v) </int,></algorithm></vector></queue></cstdio>…
問題 解法 グラフの2彩色判定をすればいい。深さ優先探索を用いるとできた。 コードに無駄ありすぎぃな感がある。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 2000; int T, N, M; bool interact[MAX_N][MAX_N]; bool used[MAX_N]; char co</algorithm></cstdio>…
問題 解法 駅は番号で管理するとやりやすい。駅名と駅番号を対応付けるためにmapをつかう。 あとはダイクストラかワーシャルフロイドすればいい。 #include <iostream> #include <cstdio> #include <vector> #include <string> #include <map> #include <queue> #include <algorithm> using namespace std; const int I</algorithm></queue></map></string></vector></cstdio></iostream>…
問題 解法 蟻本を参考にした。 最小全域木を求めればいいみたい。 連結成分ごとにプリム法を行うというやりかたをした。 #include <cstdio> #include <algorithm> #include <vector> #include <queue> using namespace std; typedef pair<int, int> P; //最小コスト、位置 const int INF = 1 << 30; const</int,></queue></vector></algorithm></cstdio>…
問題 グラフの頂点1からNまでの経路のうち、二番目に短いものの長さを求めよ。 解法 蟻本を参考にした。 ダイクストラ法を使って最短路と二番目の最短路を更新しながら計算していく。 #include <cstdio> #include <algorithm> #include <queue> #include <vector> using namespace std; typedef</vector></queue></algorithm></cstdio>…
問題 解法 ダイクストラ法を使って、ああでもないこうでもないとやっている うちになぜか解けてしまったのでよくわからない。 動的計画法も使っているような気がする…だけかもしれない。 割引券の枚数に対する最短距離？みたいなのを計算していく？というよ…
問題 解法 ダイクストラ法で解いた。 うろ覚えで書いて正直通ると思っていなかったのに、通ってうれしい。 #include <cstdio> #include <queue> #include <vector> #include <algorithm> using namespace std; typedef pair<int ,int> P; //first 距離 second 位置 const int MAX_N = 100, INF = 1 << 30;</int></algorithm></vector></queue></cstdio>…
問題 解法 有向グラフの最短経路を求める問題。 ワーシャルフロイド法をつかえば十分はやく求まる。 #include <cstdio> #include <algorithm> using namespace std; const int INF = 1 << 29; const int MAX_N = 21; int G[MAX_N][MAX_N]; int N, s, g; int HOUBI, HASHIRA; int</algorithm></cstdio>…
アルゴリズムデザインにのっていた問題。 本当は動的計画法を使うらしいけど、よく分からないので、BFSした。問題 木が与えられる。この木の根から情報を発信する。情報は、時間１の間に各ノードから そのノードの１つの子ノードにしか送ることができない。 …
問題 うわさを広げたい。ある人から他の人へうわさが伝わるのにかかる時間がそれぞれあたえられる。 この時、一番はじめに誰にうわさを吹き込めば一番早くうわさが全体に広がるかを 計算し、さらにかかる時間を求めるプログラムを作れ。解法 重み付き有向グ…
グラフ理論の勉強によさげなのがあったのでリンクを貼っておく。 北海道大学 グラフ理論講義ノート
有名な「僕は友達がいない」の問題 直接の友達の数を数える->友達の友達を数える の順番でプログラムをつくる。 直接の友達にしるしをつけておいて、友達の友達を判断する。 このとき、友達の友達にも、しるしを付けないと重複して数えてしまうので注意する…
