글 읽기 - 크루스칼 알고리즘 틀렸습니다.

rdd6584 7년 전 0

테스트케이스 및 기타 제가 생각한 예제 모두 통과하는데 왜 안되는지 모르겠습니다.

도와주세요.

#include<stdio.h>
#include<stdlib.h>

#define MAX 1000

typedef struct {
	long long int value;
	int x;
	int y;
} data;

data mat[MAX*MAX];


//Union-find 시작
int parent[MAX];
int num[MAX];

void set_init(int n)
{
	int i;
	for (i = 0; i < n; i++) {
		parent[i] = -1;
		num[i] = 1;
	}
}

int set_find(int vertex)
{
	int p, s, i = -1;
	for (i = vertex; (p = parent[i]) >= 0; i = p)
		;
	s = i;
	for (i = vertex; (p = parent[i]) >= 0; i = p)
		parent[i] = s;
	return s;
}

void set_union(int s1, int s2)
{
	if (num[s1] < num[s2])
	{
		parent[s1] = s2;
		num[s2] += num[s1];
	}
	else {
		parent[s2] = s1;
		num[s1] += num[s2];
	}
}
//union-find 끝

int compare(void *k1, void *k2)
{
	return (*(int *)k1 - *(int *)k2);
}


int main()
{
	int n;
	int m;
	int uset, vset;
	long long int sum = 0;
	int count = 0;

	scanf("%d", &n);
	scanf("%d", &m);

	for (int i = 0; i < m; i++)
		scanf("%d %d %lld", &mat[i].x, &mat[i].y, &mat[i].value);

	qsort(mat, m, sizeof(mat[0]), compare);
	set_init(n);

	for (int i = 0; count < n - 1; i++)
	{
		uset = set_find(mat[i].x);
		vset = set_find(mat[i].y);
		if (uset != vset)
		{
			sum += mat[i].value;
			set_union(uset, vset);
			count++;
		}
	}

	printf("%lld", sum);
}

rhs0266 7년 전 1

uset, vset 은 0번지부터, 입력은 1번부터 여서 indexing에 1차이가 납니다.

배열 크기를 1000보다 크게 잡아주세요.

rdd6584 7년 전 0

앗 그렇군요 ㅠㅠㅠ 정말 매번 감사합니다.

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

문제

문제

출처

ICPC

크루스칼 알고리즘 틀렸습니다.

rdd6584 7년 전 0

rhs0266 7년 전 1

rdd6584 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말