olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

2019-08-03から1日間の記事一覧

Codeforces Round #576 (Div. 1)C-Matching vs Independent Set

問題概要 3N頂点M辺の単純無向グラフがある。このグラフから次のどちらかを取り出したい。 ・互いに辺で結ばれていないサイズNの頂点集合 ・互いに頂点を共有していないサイズNの辺集合 解法 全ての辺を好きな順番で見ていき、これまでに辺集合に追加し…