문제
그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.
입력
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.
그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.
출력
첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.
예제 입력
3 3 1 2 1 2 3 2 1 3 3
예제 출력
3
문제 풀이
최소 스패닝 트리 테스트하는 문제이다.
답안 코드
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_V 10000
int V,E;
vector<int> adj[MAX_V+1];
vector<pair<int, pair<int,int>>> edges;
int unionGroup[MAX_V+1];
int find(int i){
while(unionGroup[i] != i)
i = unionGroup[i] = unionGroup[unionGroup[i]];
return i;
}
void unionSet(int u, int v){
u = find(u);
v = find(v);
unionGroup[u] = v;
}
bool isUnion(int u, int v){
return find(u) == find(v);
}
int main(){
scanf("%d %d", &V, &E);
for(int i = 0; i < E; ++i){
int u,v,w;
scanf("%d %d %d", &u, &v, &w);
edges.push_back(make_pair(w, make_pair(u, v)));
}
sort(edges.begin(),edges.end());
for(int i = 1; i <= V; ++i)
unionGroup[i] = i;
int mst_cost = 0;
for(int i = 0; i < edges.size(); ++i){
auto e = edges[i].second;
if(!isUnion(e.first, e.second)){
mst_cost += edges[i].first;
unionSet(e.first, e.second);
}
}
printf("%d\n", mst_cost);
return 0;
}
Leave A Comment