heavy light decompositionを試したのでLCAの問題にsubmit。 参考にした資料 http://math314.hateblo.jp/entry/2014/06/24/220107問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C #include<iostream> #include<vector> #include<algorithm> #define REP(i, n) for</algorithm></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C&lang=jp参考スライド http://www.slideshare.net/iwiwi/2-12188845Link Cut TreeでLCAをやってみました。 Link Cut Tree部分はほとんど参考スライドのものと同じです。 #include<iostream> #</iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0294 解説 http://web-ext.u-aizu.ac.jp/pc-concours/2014/download/pastexam/editorial2013_final.pdf私は書籍「最新コンパイラ構成技法」のLengauer-Tarjanの擬似コードを参考にしました…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1156 g[現在の方向][Y][X]:=最短距離 でダイクストラ。 #include<iostream> #include<vector> #include<algorithm> #include<queue> #define rep(i,n) for(int i=0;i<(n);i++) #define INF (1<<29) #define Cost first.first #d</queue></algorithm></vector></iostream>…

問題文 http://poj.org/problem?id=3169蟻本で解説されてる問題。やっと理解した。不等式制約の双対をとると最短経路問題になる。 #include <iostream> #include <vector> #include <algorithm> #define MAX_V 1001 #define MAX_E 30000 #define INF (1<<29) using namespace std; struct </algorithm></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1318無向グラフが与えられるので、車にのってsからtに行くときの最短経路を求めよ。ただし車には燃料の容量がある。車は燃料1で距離10進むことができる。次の町に着いたときに燃料がちょう…

問題文 https://icpcarchive.ecs.baylor.edu/external/36/3673.pdfn×nの黒と白のグリッドが与えられる。任意の行と行、列と列をスワップすることができる。この操作を繰り返すことで、縦と横の番号が同じようなマスを全て白にできるか判定せよ。 斜めに並べ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2151 拡張ダイクストラした。 d[ ノード番号 ][ ノードについた時の残金 ] := 襲われた人数優先順位付きキューは、 P3( 襲われた人数 , P( 残金 , ノード番号 ) ) としている。 #include <iostream> </iostream>…

問題文 https://icpcarchive.ecs.baylor.edu/external/42/4210.pdfグラフが与えられる。最短経路に含まれる辺をひとつも使わない経路の中で最短のものを求めよ。ただし最短経路は複数ある場合もある。 ダイクストラを2回やる。一回目で最短経路に含まれる辺…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1140&lang=jp 幅優先探索でスタート位置と汚れについて全点対間最短距離を求めておいて、パスを全部試す。 #include<iostream> #include<vector> #include<algorithm> #include<string> #include<queue> #define INF 100000000 #define </queue></string></algorithm></vector></iostream>…

問題文 http://poj.org/problem?id=3692 最大クリーク問題。 二部グラフになっているので補グラフの最大独立集合を求める。 最大クリーク=補グラフの最大独立集合 が成り立つ。また二部グラフなら、 最大独立集合=頂点数-最大マッチング が成り立つ。 #inclu…

問題文 http://poj.org/problem?id=3180N頭の牛がM本のロープでつながれている。 タンクの周りを正しく踊れている牛のグループの数を求めよ。 強連結成分分解して、含まれている頂点の数が2以上の強連結成分の数を数えた。 #include<iostream> #include<vector> #include<algorithm> using</algorithm></vector></iostream>…

問題文 http://uva.onlinejudge.org/external/114/11463.html ワーシャルフロイドで全点間の最短距離を求めておいて、始点sと始点から最も遠い頂点の距離と、その頂点から終点dまでの距離を求めた。 #include<iostream> #include<algorithm> #define INF 10000000 using namespace</algorithm></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1055&lang=jp 連結でないグラフが与えられる。このグラフの連結成分は全て輪になっている。この連結成分からコストが最大の辺を一つだけ消してできるものがクランである。 よって一つの連…

問題文 http://uva.onlinejudge.org/external/115/11506.htmlコンピュータを頂点、ケーブルを辺とした無向グラフが与えられる。 コンピュータとケーブルを破壊して番号1のコンピュータから 番号Mのコンピュータへのパスをなくしたい。 コンピュータとケーブ…

問題文 http://uva.onlinejudge.org/external/103/10308.html重み付きの無向の木が与えられるので 最遠頂点間の距離(木の直径と言う)を求める問題。 木の直径は２回の深さ優先探索で求めることができる。 まず適当な頂点から深さ優先探索して最も遠い頂点vを…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2361 ダイクストラでソートされた状態から全ての状態までの最短経路を 求めて、その中で最長のもののコストを出力した。各ノードはvec[4]={1,2,3,4}だったら、0001 0010 0011 0100のように…

重みなし無向グラフが与えられるので、 1からn駅までz回のステップで行けるかどうか判定する問題。 ただし直前の駅には戻れない。 z回のステップで1からnまで行くパターン数はグラフの隣接行列のn乗。 ノードを(現在の駅,直前の駅)としてグラフの隣接行列を…

sからgへの最小コストを求める問題。 まず各会社ごとに、その会社の路線だけを使った全駅間の最短経路を求める。 各会社ごとに運賃表も作っておく。 そうしたら上の二つを使って各会社ごとの全駅間の最小コストが求めれる。 この各会社のグラフから、各駅間…

DAGが与えられるので、最長経路を求める問題。 ただしノードPで作業を開始するためには Pまでの最長日数が経っている必要がある。トポロジカルソートしてからDPした。 dp[i]:=結合点iまでの最長日数 #include<iostream> #include<algorithm> #include<vector> #define INF 100000000 using</vector></algorithm></iostream>…

スタート地点と1~nのチーズがおいてあるグリッドが与えられるので チーズを順番に取っていったときの最短経路の長さを求める問題。幅優先探索でiとi+1の間の最短経路をそれぞれ求めた。 #include<iostream> #include<vector> #include<algorithm> #include<string> #include<queue> #define mp make_pair </queue></string></algorithm></vector></iostream>…

東西方向と南北方向に走る通りの名前の付け方が ありうるかどうか判定する問題。通りが平行でないかはグラフを２色に彩色して 色が異なっているかで判定。水準の判定は、交差点の入力にA-BがあればA→Bの辺を張り、 AとBが同水準ならA→BとA←Bの辺を張る。 こ…

全てのショッピングモールのある街から グラフの辺上も含めて最長距離を求める問題。 ショッピングモールのある街を全てスタート地点として 最初にキューにプッシュしてダイクストラする。d[i]:=i番目の街からショッピングモールのある街への最短距離とする…

¨01234567¨を作るまでの最短手数。 幅優先探索で¨01234567¨からすべての 状態までの操作回数をmapに作っておく。 #include<iostream> #include<string> #include<algorithm> #include<queue> #include<map> using namespace std; int dx[4]={1,-1,4,-4}; map<string,int>res; void bfs(void){ queue<string>que; que.push("</string></string,int></map></queue></algorithm></string></iostream>…