ferinの競プロ帳

競プロについてのメモ

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

第5回 ドワンゴからの挑戦状 本選 C - Interval and MST

問題ページ 解法 boruvka法を使って最小全域木問題を解く。各連結成分から他の連結成分へつなぐ最もコストが小さい辺をO(N)やO(NlogN)程度で求められるときに有効な方法になる。ある区間が他の区間と交差するのは4パターンに分類できる。 その区間の右側と他…