글 읽기 - 크루스칼로 풀었는데 어디가 틀렸을까요?

kwhy2345 4년 전 0

최소 비용을 가지는 간선부터 같은 집합에 있는 정점들을 고르지 않게 체크하면서 간선 비용을 더하는 크루스칼 식으로 구현해보았습니다. 어떤점이 틀렸는지 궁금합니다.

#include <iostream>
#include <algorithm>
using namespace std;
struct vertex {
	int v1, v2, w;
};
vertex v[111111];
int n, m, k, a[1111], s;
int com(vertex a, vertex b) {
	return a.w < b.w;
}
int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < m; i++)
		cin >> v[i].v1 >> v[i].v2 >> v[i].w;
	sort(v, v + m, com);
	for (int i = 0; i < m; i++) {
		if (a[v[i].v1] && a[v[i].v1] == a[v[i].v2]) continue;
		else {
			s += v[i].w;
			if (!a[v[i].v1] && !a[v[i].v2]) a[v[i].v1] = a[v[i].v2] = ++k;
			else if (!a[v[i].v1]) a[v[i].v1] = a[v[i].v2];
			else if (!a[v[i].v2]) a[v[i].v2] = a[v[i].v1];
			else {
				int z = min(a[v[i].v1], a[v[i].v2]), x = max(a[v[i].v1], a[v[i].v2]);
				for (int j = 1; j <= n; j++)
					if (a[j] == x)
						a[j] = z;
			}
		}
	}
	cout << s;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

크루스칼로 풀었는데 어디가 틀렸을까요?

kwhy2345 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말