글 읽기 - (kruskal 알고리즘) 왜 틀렸는지 도저히 모르겠습니다 ㅠㅠ 조언 부탁드립니다

hoxymola 3년 전 0

처음으로 크루스칼 알고리즘을 구현해봤습니다

예제랑 질문 게시판에 있는 반례는 잘 돌아가는 것 같은데 제출할때마다 틀립니다 ㅠㅠ

조언이나 반례 알려주시면 정말 감사하겠습니다

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define lld long long

struct edge{
	int u;
	int v;
	double w;
};
struct cdnt {
	int y;
	int x;
};
void merge(struct edge* tmp, struct edge* psg, int l, int r);
void mergesort(struct edge* tmp, struct edge* psg, int l, int m, int r);
int FIND(int* root, int A);
void UNION(int* root, int A, int B);
double dist(struct cdnt A, struct cdnt B);
int main(void) {
	int N, M, in1, in2;
	int idx = 0;
	int count = 0;
	double sum = 0.0;
	int* root;
	struct cdnt* god;
	struct edge* psg;
	struct edge* tmp;

	scanf("%d %d", &N, &M);
	root = (int*)malloc(sizeof(int) * N);
	god = (struct cdnt*)malloc(sizeof(struct cdnt) * N);
	psg = (struct edge*)malloc(sizeof(struct edge) * N * N);
	tmp = (struct edge*)malloc(sizeof(struct edge) * N * N);
	for (int i = 0; i < N; i++) {
		root[i] = i;
		scanf("%d %d", &god[i].x, &god[i].y);
	}
	for (int i = 0; i < N; i++)
		for (int j = i + 1; j < N; j++) {
			psg[idx].u = i;
			psg[idx].v = j;
			psg[idx++].w = dist(god[i], god[j]);
		}
	merge(tmp, psg, 0, idx - 1);

	for (int i = 0; i < M; i++) {
		scanf("%d %d", &in1, &in2);
		UNION(root, in1 - 1, in2 - 1);
		count++;
	}
	for (int i = 0; i < idx; i++) 
		if (FIND(root, psg[i].u) != FIND(root, psg[i].v)) {
			UNION(root, psg[i].u, psg[i].v);
			sum += psg[i].w;
			count++;
			if (count == N - 1) {
				printf("%.2lf\n", round(sum * 100) / 100);
				break;
			}
		}

	free(root);
	free(god);
	free(psg);
	free(tmp);
	return 0;
}
void merge(struct edge* tmp, struct edge* psg, int l, int r) {
	if (l < r) {
		int m = (l + r) / 2;
		
		merge(tmp, psg, l, m);
		merge(tmp, psg, m + 1, r);
		mergesort(tmp, psg, l, m, r);
	}
}
void mergesort(struct edge* tmp, struct edge* psg, int l, int m, int r) {
	int ll = l;
	int rr = m + 1;
	int idx = 0;

	while (ll <= m && rr <= r)
		if (psg[ll].w < psg[rr].w)
			tmp[idx++] = psg[ll++];
		else
			tmp[idx++] = psg[rr++];
	while (ll <= m)
		tmp[idx++] = psg[ll++];
	while (rr <= r)
		tmp[idx++] = psg[rr++];
	for (int i = l; i <= r; i++)
		psg[i] = tmp[i - l];
}
int FIND(int* root, int A) {
	if (root[A] == A)
		return A;
	else
		return root[A] = FIND(root, root[A]);
}
void UNION(int* root, int A, int B) {
	A = FIND(root, A);
	B = FIND(root, B);
	root[A] = B;
}
double dist(struct cdnt A, struct cdnt B) {
	lld y2 = ((lld)A.y - B.y) * ((lld)A.y - B.y);
	lld x2 = ((lld)A.x - B.x) * ((lld)A.x - B.x);
	return sqrt(y2 + x2);
}

hoxymola 3년 전 0

M개의 연결 된 통로를 입력받을때

FIND(in1) != FIND(in2) 일때만 UNION을 해줘서 해결했습니다

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

문제

문제

출처

ICPC

(kruskal 알고리즘) 왜 틀렸는지 도저히 모르겠습니다 ㅠㅠ 조언 부탁드립니다

hoxymola 3년 전 0

hoxymola 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말