けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

部分グラフ列挙問題

AtCoder ABC 328 E - Modulo MST (?色, 475 点)

next_combination を使った! 普通に STL の next_permutation() でもできる。 問題へのリンク 問題概要 頂点数 、辺数 の連結な重み付き無向グラフが与えられる。 このグラフの全域木をすべて考えたときの、全域木に含まれる辺の重みの総和を で割ったあま…

AtCoder ABC 213 G - Connectivity 2 (橙色, 600 点)

面白かった!! より一般化した問題 (グラフの頂点集合の任意の部分集合に対して、それらを連結にする辺の選び方の数え上げ) を考えた方が考えやすいね。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ が与えられます。 の辺集合の部分集合 ( 通…

Codeforces Round #684 (Div. 1) B. Graph Subset Problem (R2600)

TLE が厳しくて話題になってた 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ [tex G] が与えられる。また、正の整数 が与えられる。 以下のいずれかの条件を満たすものが存在するかどうかを判定し、存在するならばそれを出力せよ。 type 1: の…

CODE FESTIVAL 2016 Final F - Road of the King (橙色, 1000 点)

面白かった!!!DEGwer さんの pdf より。 問題へのリンク 問題概要 頂点のグラフが与えられる。初期状態では 1 本も辺が張られていない。 このグラフに、頂点 1 を始点とする長さ のウォークをとり、ウォークに沿って有向辺を張っていく。有向辺の張られた…

AOJ 3169 Pyramid Graph (HUPC 2020 day1-F)

ゴリ (prd さん) と一緒に出て楽しかったコンテスト。 そして「グラフのサイクル・パスの列挙」に関する問題は北大セットの定番というイメージになってきた。 問題へのリンク 問題概要 下図のような 角錐が与えられる (底面が 角形で "頂点" の頂点番号を 0 …