글 읽기 - (6497-전력난 ) 뭐가 잘못된걸까요?

stella6767 3년 전 0

초보인데 무슨 이유인지 잘 모르겠네여..

크루스칼 알고리즘을 활용해서 최대비용에서 최소비용을 빼는 문제 아닌가여?

왜 오답인지 설명해주실 분 ㅠㅠㅠ

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


// 부모 노드(더 작은 숫자의 노드)를 가져옴 
int getParent(int set[], int x) {
	if (set[x] == x) return x;
	return set[x] = getParent(set, set[x]);
}

// 부모 노드를 병합 
void unionParent(int set[], int a, int b) {
	a = getParent(set, a);
	b = getParent(set, b);
	// 더 숫자가 작은 부모로 병합 (1하고 7이 연결되있으면 1이 7의 부모노드)
	if (a < b) set[b] = a;
	else set[a] = b;
}

// 같은 부모를 가지는지 확인
int find(int set[], int a, int b) {
	a = getParent(set, a);
	b = getParent(set, b);
	if (a == b) return 1;
	else return 0;
}

// 간선 클래스 선언 
class Edge {
public:
	int node[2];
	int distance;
	Edge(int a, int b, int distance) {
		this->node[0] = a;
		this->node[1] = b;
		this->distance = distance;
	}
	bool operator <(Edge& edge) { //sort 함수 연계
		return this->distance < edge.distance;
	}
};

int main(void) {
	
	int n, m;
	
	int a, b, c;

	cin >> n >> m;


	vector<Edge> v;

	for (int i = 0; i < m; i++)
	{
		cin >> a >> b >> c;
		v.push_back(Edge(a,b,c));
		
		if (i == m - 1) cout << "0 0"<<endl;
	}



	// 간선의 비용으로 오름차순 정렬 
	sort(v.begin(), v.end());
	//작은 거리가중치부터 먼저 시작되니까 나중에 중복되는 간선값을 넘기는 건 무조건 이 간선가중치보다 큰 값.
	//따라서 나중에 최소신장트리 만들기에 적합 

	int* set = new int[n]; //배열 동적할당
	for (int i = 0; i < n; i++) {
		set[i] = i; //일단 각자의 부모노드는 각자노드로 정한다.
	}

	// 거리의 합을 0으로 초기화 
	int sum = 0;
	int max = 0;

	for (int i = 0; i < v.size(); i++) {
		// 동일한 부모를 가르키지 않는 경우, 즉 사이클이 발생하지 않을 때만 선택 
		if (!find(set, v[i].node[0] , v[i].node[1])) {	
			sum += v[i].distance;
			unionParent(set, v[i].node[0] , v[i].node[1] );
			
		}
	}

	printf("%d\n", max-sum); 


	delete[] set;
}

kms9937 3년 전 0

입력은 여러개의 테스트 케이스로 구분되어있다고 문제에 나와있습니다.

stella6767 3년 전 0

입력은 여러개의 테스트 케이스로 구분되어있다.. 무슨 말인지 잘 모르겠는데요...

kms9937 3년 전 1

입력의 끝에서는 첫 줄에 0이 2개 주어진다.

즉 0,0이 입력될 때까지 계속 반복해 주시면 됩니다.

stella6767 3년 전 0

감사합니당 ㅠㅠ 다른 답안 뒤져보고 실행하다보니 무슨 말인지 알 것 같네요. 조금만 시도해보고 해결됨으로 바꿀게요 ㅠㅠㅠ

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

문제

문제

출처

ICPC

(6497-전력난 ) 뭐가 잘못된걸까요?

stella6767 3년 전 0

kms9937 3년 전 0

stella6767 3년 전 0

kms9937 3년 전 1

stella6767 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말