글 읽기 - 왜 outofbounds 가 뜨는지 모르겠습니다 ㅠㅠ

sujipark2009 2년 전 0

크루스칼 알고리즘으로 풀어보려는 중인데 9%에서 outofbounds가 뜹니다

예제와 질문에 있는 반례 몇가지는 다 통과했습니다

공간은 충분하게 만들어놓고 시작한거같은데 어느부분에서 터지는지 못 찾겠습니다...

#include <stdio.h>
#include <math.h>
#include <limits.h>

typedef struct pos {
	int x;
	int y;
	int idx;
}Pos;

typedef struct edge {
	Pos v1;
	Pos v2;
	long double d;
}Edge;


int n, m;
int min;
Pos p[1005];
Edge e[1000001];
int U[1005];
int cnt;
int cnt2;
long double res;

void makeset(int i)
{
	U[i] = i;
}
void init(int n)
{
	for (int i = 1; i <= n; i++)
	{
		makeset(i);
	}
}
int find(int i)
{
	int j = i;
	while (U[j] != j)
		j = U[j];
	return j;
}
int equal(int p, int q)
{
	int a = find(p);
	int b = find(q);
	return a == b ? 1 : 0;
}
void merge(int p, int q)
{
	U[p] = q;
}

long double dist(Pos a, Pos b)
{
	long long x = a.x - b.x;
	long long y = a.y - b.y;
	return sqrt((x * x) + (y * y));
}

void findDist()
{
	for (int i = 2; i <=n; i++)
	{
		Pos a;
		a.x = p[i].x;
		a.y = p[i].y;
		a.idx = p[i].idx;
		for (int j = 1; j < i; j++)
		{
			Pos b;
			b.x = p[j].x;
			b.y = p[j].y;
			b.idx = p[j].idx;

			long double d = dist(a, b);

			e[cnt].v1 = a;
			e[cnt].v2 = b;
			e[cnt].d = d;
			cnt++;
		}
	}
}

int compare(void* a, void* b)
{
	Edge* n1 = (Edge*)a;
	Edge* n2 = (Edge*)b;

	if ((*n1).d > (*n2).d)
		return 1;
	if ((*n1).d == (*n2).d)
		return 0;
	else
		return -1;
}

void solve()
{
	int i, j;
	Pos a, b;
	while (1)
	{
		if (m + cnt2 == n-1)break;
		a = e[cnt2].v1;
		b = e[cnt2].v2;
		i = find(a.idx);
		j = find(b.idx);
		if (!equal(i, j)) {
			merge(i, j);
			res += e[cnt2].d;
		}
		cnt2++;
	}
}

int main(void)
{
	int p1, p2;
	int a, b;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <=n; i++)
	{
		scanf("%d %d", &p1, &p2);
		p[i].x = p1;
		p[i].y = p2;
		p[i].idx = i;
	}
	init(n);

	for (int i = 0; i < m; i++)
	{
		scanf("%d %d", &p1, &p2);
		a = find(p1);
		b = find(p2);
		if (!equal(a, b)) {
			merge(a, b);
		}
	}
	findDist();
	qsort(e, cnt, sizeof(Edge), compare);

	solve();

	printf("%.2lf", res);
}

djm03178 2년 전 1

107번째 줄의 조건이 잘못되었습니다. 처음부터 주어진 m개의 간선이 이미 사이클을 가진 형태일 수도 있습니다. 즉, 불필요한 간선이 이미 처음부터 주어져있을 수도 있기 때문에 최종 상태가 트리 형태가 될 것이라고 단정지을 수 없습니다.

sujipark2009 2년 전 0

역시 저기가 문제였군요.. 감사합니다 ㅠ.ㅠ

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

문제

문제

출처

ICPC

왜 outofbounds 가 뜨는지 모르겠습니다 ㅠㅠ

sujipark2009 2년 전 0

djm03178 2년 전 1

sujipark2009 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말