[C++]백준 1197번 : 최소 스패닝 트리

[C++]백준 1197번 : 최소 스패닝 트리

https://www.acmicpc.net/problem/1197

1. 풀이

정직한 최소 스패닝 트리 문제

https://dmzld.tistory.com/34

이전에 올린 관련 이론 정리

#include #include #include using namespace std; struct info { int a, b, c; }; struct comp { bool operator()(info a, info b) { return a.c > b.c; } }; int V, E, A, B, C; int p[10001]; priority_queue, comp> pq; int res; int find(int x) { if (p[x] == x) return x; else return p[x] = find(p[x]); } void merge(int x, int y) { int px = find(x); int py = find(y); p[max(px, py)] = min(px, py); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> V >> E; for (int i = 0; i < E; i++) { cin >> A >> B >> C; pq.push({ A, B, C }); } for (int i = 1; i <= V; i++) p[i] = i; while (!pq.empty()) { info tmp = pq.top(); pq.pop(); if (find(tmp.a) == find(tmp.b)) continue; else { merge(tmp.a, tmp.b); res += tmp.c; } } cout << res; return 0; }

다른 블로그 찾아봤는데 굳이 pq 안쓰고 vector, sort로 풀이하시더라

from http://dmzld.tistory.com/61 by ccl(A) rewrite - 2021-09-09 06:26:48