Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

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

【TTPC2019-F Road Construction】グラフの変形

コンテスト中に解けなかったので解いておきます。 F - Road Construction 問題 コストつきのグラフが与えられる。これらの辺は最初、有効になっていない。このうち、いずれかの辺を有効化して、wからx、yからzの両方が通るようにしたい。最小のコストはいく…

閉路検出アルゴリズム

ABC139のEで閉路の話が出てきたので、閉路について調べようと思いました。 UFを使って無向グラフの閉路を検出するアルゴリズム 知らなかったです;; www.youtube.com 無向グラフにおいて閉路検出する方法は、有向グラフと見てDFSでやっていくというのが一つ…