最小カットを使って「燃やす埋める問題」を解く方法について、問題とソースコードつきで、まとめました。ニコニコ生放送「TopCoderでプログラムしてみた」2000回記念放送の資料です。
![Union find(素集合データ構造)](https://cdn-ak-scissors.b.st-hatena.com/image/square/7927be9fd3c04d6159d78013593a82bebedde5ca/height=288;version=1;width=512/https%3A%2F%2Fcdn.slidesharecdn.com%2Fss_thumbnails%2Funion-find-150606111755-lva1-app6892-thumbnail.jpg%3Fwidth%3D640%26height%3D640%26fit%3Dbounds)
最小カットを使って「燃やす埋める問題」を解く方法について、問題とソースコードつきで、まとめました。ニコニコ生放送「TopCoderでプログラムしてみた」2000回記念放送の資料です。
foreach 辺e in E in ascending order if 採用した辺集合にeを加えても閉路を作らない then eを採用 return 採用した辺のコストの和 辺をコストの小さい順で走査するのは、辺情報を格納した配列を事前にソートすれば簡単に実現できます。 問題はすでに採用済みの辺の集合にeを追加したときに閉路を作るかどうかの判定です。 この判定にはUnion Findというデータ構造を利用します。 Union Find (素集合データ構造) Union Findは、n個のデータがn個のグループ(集合)のどれかに属しているようなグループ群に対し、 unite(x,y):2つのデータx, yが属するグループをマージする find(x):データxが属するグループを求める という処理を効率よく行えるデータ構造です。 Union Findにはいくつか種類がありますが、ここでは木構
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く