글 읽기 - Union-find로는 안되는 건가요?

ispark 6년 전 0

Union-find로 풀어 보았습니다.

40% 정도 가다가 틀림으로 나옵니다.

아이디어는 선후관계가 주어질 때마다 union을 해주고 앞선 사건에 가중치를 줍니다.

이 가중치의 합을 가지고 요구되는 두 사건의 선후관계를 알수 있지 않을까 해서 입니다.

(교수님을 기다려주지 않는다 문제 응용)

잘못된 아이디어 일까요? 고수님들의 도움 부탁 드립니다.

#include <stdio.h>
#define MAXN 405

int n, k, s, par[MAXN], sum[MAXN];

int find(int x)
{
	if (x == par[x]) return x;
	int xx = find(par[x]);
	sum[x] += sum[par[x]];
	return par[x] = xx;
}

int main()
{
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++) par[i] = i;

	int a, b;
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &a, &b);
		int p = find(a), q = find(b);
		par[p] = q;
		sum[p] = -sum[a] + 1 + sum[b];
	}
	scanf("%d", &s);
	for (int i = 1; i <= s; i++) {
		scanf("%d %d", &a, &b);
		if (find(a) == find(b)) printf("%d\n", sum[a] > sum[b] ? -1 : 1);
		else printf("0\n");
	}
	return 0;
}

jwvg0425 6년 전 0

저는 일단 플로이드로 풀긴 했는데 union-find로도 풀리는지 아닌진 잘 모르겠네요 다른 고수분이 답변해주실 듯

ispark 6년 전 1

아..Union-find로는 어렵겠네요..

교수님을 기다려주지 않는다와는 다른 케이스 입니다. 교수님은..에서는 1 2 3, 1 3 2 (세번째가 무게) 같이 주어졌을 때 2번과 3번의 무게차이를 알 수 있는 반면에

이 문제에서는 알 수 없습니다. (빠른 방법을 찾았다고 좋아했었는데요 ㅠㅠ)

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

문제

문제

출처

ICPC

Union-find로는 안되는 건가요?

ispark 6년 전 0

jwvg0425 6년 전 0

ispark 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말