MST

D. Maximum Distance

Quiz https://codeforces.com/problemset/problem/1081/D AC https://codeforces.com/contest/1081/submission/92692968 問題理解 最初、max, min, cost, distanceで混乱した costについては「経路上の1番高いコストの切符を買えば、他は無料」と考える spec…

最小全域木 MST (minimum spanning tree) O(ElogE)

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を使う エッジコストの小さい順に取り出…