글 읽기 - 왜 틀렸는지 모르겠습니다ㅜㅜ

sminhyuck 4년 전 0

에지들의 가중치를 기준으로 내림차순 하여 UNION FIND 하는 방식으로 만족값을 구하는 코드입니다.

UNION을 하면서 만족값을 계산하는데, 어디가 틀린지 어떻게 고쳐야할지 모르겠습니다

고수분들 조언좀 부탁드립니다 ㅠㅠ

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

struct EDGE {
	int X, Y, W;
};

bool COMP(const EDGE &a, const EDGE &b) {
	return a.W > b.W;
}// 가중치 기준 내림차순

EDGE E[99999];
int TREE[100001], COUNT[100001], N;
long long ANSWER;

void INIT() {
	ANSWER = 0;
	cin >> N;
	for (int i = 0; i < N-1; i++) {
		cin >> E[i].X >> E[i].Y >> E[i].W;
		TREE[i + 1] = i + 1;
		COUNT[i+1] = 1;
	}
	TREE[N - 1] = N - 1; COUNT[N - 1] = 1;
	TREE[N] = N; COUNT[N] = 1;
	sort(E, E + N, COMP);
}

int find(int u) {
	if (u == TREE[u]) return u;
	return TREE[u] = find(TREE[u]);
}

void UNION(int u, int v, int w) {
	u = find(u);
	v = find(v);
	if (u == v) return;
	if (COUNT[u] > COUNT[v]) swap(u, v);	// 항상 u가 더 작은 트리가 되게끔

	if (COUNT[u] == 1) { ANSWER += COUNT[v] * w; COUNT[v]++; }
	else { ANSWER += COUNT[v] * COUNT[u] * w; COUNT[v] += COUNT[u] - 1;}

	TREE[u] = v;
}

void CALC() {
	for (int i = 0; i < N-1; i++) {
		int u, v, w;
		u = E[i].X;
		v = E[i].Y;
		w = E[i].W;
		UNION(u, v, w);
	}
	cout << ANSWER << endl;
}

int main() {
	INIT();
	CALC();
}

sait2000 4년 전 1

제목에 스포 당해서 풀어버렸잖아요 ㅠㅠ 42번 줄에 보시면 착각하기 쉬운데 - 1 하시면 안 됩니다.

sminhyuck 4년 전 0

죄송합니다 ㅠㅠ 스포되지 않도록 제목 수정했습니다!

그런데 말씀해주신 42번째 줄 -1 부분 이해했고, -1을 제거해서 제출하였는데 틀렸습니다가 발생합니다..

예제에도 맞고, 개인적으로 짜서 돌려도 제대로 나오는데 어디서 문제인걸까요? ㅠㅠ

sait2000 4년 전 1

전체 답 뿐만이 아니라 42번 줄 곱셈도 오버플로우가 날 수 있습니다. 50000짜리 2개를 199로 합친다고 생각해보세요

sait2000 4년 전 1

지금 보니까 제 예제가 틀렸네요 200까지인데 W가

sminhyuck 4년 전 0

넵 그래서 자료형을 long long 으로 했는데 그래도 오버플로우가 발생할까요? ㅠㅠ

어제 하루종일을 이것만 붙잡고 있었는데, 아직 해결을 못했네요 ㅠㅠㅠㅠ

sminhyuck 4년 전 0

이 상태에서 진전이 없습니다....

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

struct EDGE { int X, Y, W; };

bool COMP(const EDGE &a, const EDGE &b) { return a.W > b.W; }// 가중치 기준 내림차순

EDGE E[99999];
int TREE[100001], COUNT[100001], N;	// 각 트리 노드의 부모를 나타냄, 트리의 개수, 정점 수
long long ANSWER;

void INIT() {
	ANSWER = 0;
	cin >> N;
	for (int i = 0; i < N-1; i++) {
		cin >> E[i].X >> E[i].Y >> E[i].W;
		TREE[i + 1] = i + 1;
		COUNT[i+1] = 1;
	}
	TREE[N - 1] = N - 1; COUNT[N - 1] = 1;
	TREE[N] = N; COUNT[N] = 1;
	sort(E, E + N, COMP);
}

int find(int u) {
	if (u == TREE[u]) return u;
	return TREE[u] = find(TREE[u]);
}

void UNION(int u, int v, int w) {
	u = find(u);
	v = find(v);
	if (u == v) return;
	if (COUNT[u] > COUNT[v]) swap(u, v);	// 항상 u가 더 작은 트리가 되게끔

	if (COUNT[u] == 1) { ANSWER += COUNT[v] * w; COUNT[v]++; }	// 새로운 에지 하나만 트리에 삽입 될 때
	else { ANSWER += COUNT[v] * COUNT[u] * w; COUNT[v] += COUNT[u];}	// 트리를 이룬 에지가 다른 트리에 삽입될 때
	TREE[u] = v;	// 트리 합치기(작은 트리가 큰 트리 아래로)
}

// 가중치로 내림차순된 에지들을 UNION 하면서 계산
void CALC() {
	for (int i = 0; i < N-1; i++) {
		int u, v, w;
		u = E[i].X;	v = E[i].Y; w = E[i].W;
		UNION(u, v, w);
	}
	cout << ANSWER << endl;
}

int main() {
	INIT();
	CALC();
}

sait2000 4년 전 1

그러니까 곱한 결과 자체가 지금 32비트에 안 들어옵니다.

COUNT[v], COUNT[u], w 모두 long long이 아니고 int라서 계산이 int로 되기 때문에 거기서 오버플로우가 나는 겁니다. 그 이미 틀린 곱셈값이 ANSWER에 더해지고 있는겁니다. 그러면 ANSWER에서 덧셈이 오버플로우가 안 나도 답이 틀리죠.

sminhyuck 4년 전 0

더하는 자료형이 long long 이면 자동으로 곱하는 값도 long long으로 처리되는줄 알았는데 그게 아니었군요!

조언해주신 덕분에 문제 해결했습니다! 감사합니다! ㅎㅎ 속이 시원하네요

좋은 하루 되세요~!

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

문제

문제

출처

ICPC

왜 틀렸는지 모르겠습니다ㅜㅜ

sminhyuck 4년 전 0

sait2000 4년 전 1

sminhyuck 4년 전 0

sait2000 4년 전 1

sait2000 4년 전 1

sminhyuck 4년 전 0

sminhyuck 4년 전 0

sait2000 4년 전 1

sminhyuck 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말