글 읽기 - 왜 이 방법으로는 안되는지 이해가 안갑니다.

alsidnf 4년 전 0

union-find를 사용했습니다. 코드 내용은 확실히 비교하려고 한부분 빼고 다 똑같이 했습니다. 메인 함수 마지막 for문에서 break가 있는 조건문의 내용만 다릅니다. 하나는 출발지와 목적지의 그룹을 직접 비교했고, 나머지 하나는 merge함수로 그룹을 이어줄 때 마다 카운트를 해서 (마을수-1)이 될 때 break해줬습니다. 직접비교가 확실한건 알겠는데, merge함수로 그룹 이어줄 때 마다 카운트하는 방식이 왜 안되는지 반례가 있는건지 아니면 구현에서 실수가 있는지 궁금합니다.ㅠㅠ

//@@@@@@@@@@@@@@@@@1번째 코드@@@@@@@@@@@@@@@
#include <cstdio>
int p, w, c, v;
int P[1001];
int cnt, min = 0x7FFFFFFF;
struct Load {
	int s;
	int e;
	int w;
}l[100010];
void quick(int left, int right)
{
	int L, R, M;
	Load temp;
	if (left < right)
	{
		L = left - 1; R = right + 1;
		M = l[(L + R) / 2].w;
		while (1)
		{
			while (l[++L].w > M);
			while (l[--R].w < M);
			if (L >= R) break;
			temp = l[L]; l[L] = l[R]; l[R] = temp;
		}
		quick(left, L - 1);
		quick(R + 1, right);
	}
}
int find(int n)
{
	if (P[n] < 0) return n;
	P[n] = find(P[n]);
	return P[n];
}
bool merge(int a, int b)
{
	a = find(a);
	b = find(b);
	if (a == b) return 0;
	if (P[a] < P[b]) {
		P[a] += P[b];
		P[b] = a;
	}
	else {
		P[b] += P[a];
		P[a] = b;
	}
	return 1;
}
int main()
{
	scanf("%d %d", &p, &w);
	scanf("%d%d", &c, &v);
	for (int i = 0; i < p; i++) P[i] = -1;
	for (int i = 0; i < w; i++)
	{
		scanf("%d %d %d", &l[i].s, &l[i].e, &l[i].w);
	}
	quick(0, w - 1);
	for (int i = 0; i < w; i++)
	{
		if (cnt == p - 1) break;
		if (merge(l[i].s, l[i].e))
		{
			cnt++;
			min = l[i].w;
		}
	}
	printf("%d", min);
}


//@@@@@@@@@@@@@@@@@2번째 코드@@@@@@@@@@@@@@@

#include <cstdio>
int p, w, c, v;
int P[1001];
int cnt, min = 0x7FFFFFFF;
struct Load {
	int s;
	int e;
	int w;
}l[100010];
void quick(int left, int right)
{
	int L, R, M;
	Load temp;
	if (left < right)
	{
		L = left - 1; R = right + 1;
		M = l[(L + R) / 2].w;
		while (1)
		{
			while (l[++L].w > M);
			while (l[--R].w < M);
			if (L >= R) break;
			temp = l[L]; l[L] = l[R]; l[R] = temp;
		}
		quick(left, L - 1);
		quick(R + 1, right);
	}
}
int find(int n)
{
	if (P[n] < 0) return n;
	P[n] = find(P[n]);
	return P[n];
}
bool merge(int a, int b)
{
	a = find(a);
	b = find(b);
	if (a == b) return 0;
	if (P[a] < P[b]) {
		P[a] += P[b];
		P[b] = a;
	}
	else {
		P[b] += P[a];
		P[a] = b;
	}
	return 1;
}
int main()
{
	scanf("%d %d", &p, &w);
	scanf("%d%d", &c, &v);
	for (int i = 0; i < p; i++) P[i] = -1;
	for (int i = 0; i < w; i++)
	{
		scanf("%d %d %d", &l[i].s, &l[i].e, &l[i].w);
	}
	quick(0, w - 1);
	for (int i = 0; i < w; i++)
	{
		if (find(c) == find(v)) break;
		if (merge(l[i].s, l[i].e))
		{
			cnt++;
			min = l[i].w;
		}
	}
	printf("%d", min);
}

hello70825 4년 전 0

굳이 모든 마을을 연결하지 않아도 됩니다.

만약 밑과 같은 입력이 들어오면 2번 코드의 경우에는 100이 출력되지만, 1번 코드의 경우에는 모든 마을을 연결시켜야하니 2가 출력되겠네요.

alsidnf 4년 전 0

아 다시 문제를 읽어보니 문제 이해를 잘 못했네요 ㅠㅠ.. 감사합니다

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

문제

문제

출처

ICPC

왜 이 방법으로는 안되는지 이해가 안갑니다.

alsidnf 4년 전 0

hello70825 4년 전 0

alsidnf 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말