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

Tamflexの貯蔵庫

やる気のない備忘録

c++11でグラフ理論

競プロで頻繁にグラフが絡む問題が出題されます. 隣接リストvector<vector<Edge>>を継承してグラフの様々な値を求めることができるクラスを作ってみました. 使い方 ・宣言 graph<T> g((int)n): 重みの型がTの,頂点の数がn個の隣接グラフの宣言. ・辺の挿入 g.direct(src,dst,</t></vector<edge>…

aoj 0086

パトロール | Aizu Online Judge 一筆書き可能か判定する問題, すなわちグラフGが与えられた時そのグラフがオイラー路であるか判定すればよい. オイラー路となる条件は, すべての頂点の次数が偶数⇔オイラー閉路(オイラーグラフ) 奇数次数の頂点が2つで残りが…

codingame - Skynet: the Virus

Ambush Finish the 4th test of the "Skynet: the virus" puzzle with 50 or more remaining links and get a 100% score. (訳) 待ち伏せ "Skynet: the virus"の4番目のテストケースを50辺以上残して完了し,100%のスコアを獲得せよ. というAcheivementがあ…

codingame - Teads Sponsored Contest

グラフの直径を求めれば良い 以下が参考になる Spaghetti Source - 木の直径前に解いたabc019のdouble sweepのアルゴリズムを思い出した. 計算量はO(E) この手の問題は多いのでそのうちグラフをクラス化して保存しておきたい. 直径,最小全域木等をg.diameter…