uos-machine-learning
1197 - 최소 스패닝 트리 본문
1<=V<=10000인 정점과 1<=E<=100,000인 간선이 주어졌을 때 최소 스패닝 트리를 구하는 문제이다.
크루스칼 알고리즘을 구현하여 제출하면 된다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct edge {
int u, v, w;
// 구조체 edge에서의 연산자 < 정의
bool operator < (const edge &other) {
return w < other.w;
}
};
int parent[10001];
int find(int x) {
if (x == parent[x]) {
return x;
}
return parent[x] = find(parent[x]);
}
void Union(int x, int y) {
x = find(x);
y = find(y);
parent[y] = x;
}
int main()
{
// 컴퓨터의 수 N, 연결할 수 있는 선의 수 M
int N, M;
cin >> N >> M;
vector<edge> Edge;
int ans = 0;
for (int m = 0; m < M; m++) {
int a, b, c;
cin >> a >> b >> c;
Edge.push_back({ a, b, c });
}
sort(Edge.begin(), Edge.end());
for (int i = 1; i <= 10000; i++) {
parent[i] = i;
}
for (int m = 0; m < M; m++) {
int x = find(Edge[m].u);
int y = find(Edge[m].v);
if (x != y) {
Union(x, y);
ans += Edge[m].w;
}
}
printf("%d", ans);
}
'알고리즘 > 문제풀이' 카테고리의 다른 글
11403 - 경로 찾기 (0) | 2019.05.11 |
---|---|
1956 - 운동 (0) | 2019.05.11 |
11779 - 최소비용 구하기 (0) | 2019.05.11 |
1916 - 최소비용 구하기 (0) | 2019.05.10 |
1922 - 네트워크 연결 (0) | 2019.05.09 |
Comments