perogram

最小全域木 MST (minimum spanning tree)

Quiz

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp

Submission

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3589709#1

解法

  • Kruskal法を使う
  • 同じグループ判定にUnion Findを使う
  • エッジコストの小さい順に取り出すためにPriority Queueを使う
    • ソート済みのvectorでもよい

小さい順に取り出すpriority_queue

// コストの小さい順に取り出す設定
priority_queue<Edge, vector<Edge>, greater<Edge> > que;

他にMSTを使う問題

類題