글 읽기 - 혹시 반례가 무엇이 있을까요?

idjjm95 2년 전 0

제가 생각한 풀이 방법은

각 좌표들마다 인덱싱을 해서

같은 부모가 아닌 별들 중 최소 거리를 가지 별을 구해서

현재 부모에 편입시키는 방향으로 풀이를 생각했습니다.

그런데 25%에서 틀렸다고 나옵니다.

어디가 문제일까요?

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;

double result = 0;
vector <pair <int, pair<double, double>>> star;
int N;
int head[100];



int find(int x)
{
	if (head[x] == x) return x;
	else return find(head[x]);
}

void Union(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x != y)
		head[y] = x;
}

bool issameparent(int x, int y)
{
	x = find(x);
	y = find(y);

	if(x==y) return true;
	return false;
}
double dist(int x, int y)
{
	return hypot(star[x].second.first - star[y].second.first, star[x].second.second - star[y].second.second);
}

void Min_idx(int x) {
	int min_idx=-1;
	double ret = 10000;
	for (int j = x + 1; j < N; j++) {
		if (!issameparent(x, j) && ret > dist(x, j))
		{
			ret = dist(x, j);
			min_idx = j;
		}
	}
	if (min_idx != -1) {
		Union(x, min_idx);
		result += ret;
	}
	return;
}




int main() {
	double num1, num2;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%lf %lf", &num1, &num2);
		star.push_back(make_pair(i, make_pair(num1, num2)));
		head[i] = i;
	}

	for (int i = 0; i < N; i++)
		Min_idx(i);

	printf("%.2lf \n", result);

	return 0;
}

55murphy 2년 전 17

아래 반례의 경우 이렇게 있는 방법이 정답입니다

하지만 질문자님 코드는 이런 방식으로 별들을 연결합니다

입력:
6
4 1
5 8
2 1
8 4
2 9
1 4
정답: 18.32
오답: 20.42

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

문제

문제

출처

ICPC

혹시 반례가 무엇이 있을까요?

idjjm95 2년 전 0

55murphy 2년 전 17

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말