글 읽기 - 13418 학교 탐방하기 문제 질문입니다.

moonsoo5522 7년 전 0

문제에서는 오르막길 코스트가 0이고, 내리막길 코스트가 1이라서, 표준 입력으로 값을 얻은 이후, 아예 0과 1을 반전해서 자료구조에 저장했습니다.

그리고 오름차순으로 정렬해서 최소 스패닝트리 코스트를 구하고

한번은 내림차순으로 정렬해서 최대 스패닝트리 코스트를 구한 다음, 두 코스트의 제곱을 빼서 답을 구했는데

틀렸다고 나오네요... 크루스칼 알고리즘 코드가 틀린 것 같진 않은데 어디가 문제인지 감이 잡히지 않습니다 ㅠㅠ

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

int root[1001];
typedef struct Edge
{
	int a, b, cost;
}Edge;
vector<Edge> e;
int N, M;

bool compare1(Edge e1, Edge e2)
{
	return e1.cost < e2.cost;
}
bool compare2(Edge e1, Edge e2)
{
	return e1.cost > e2.cost;
}
int find(int n)
{
	if(root[n] == n)
		return n;
	
	return root[n] = find(root[n]);
}
long long process(bool (*comp)(Edge e1, Edge e2))
{
	sort(e.begin(), e.end(), comp);
	
	for(int i=0; i<=N; i++)
		root[i] = i;
	
	int a, b, cost;
	long long sum = 0;
	for(int i=0; i<e.size(); i++)
	{
		a = e[i].a;
		b = e[i].b;
		cost = e[i].cost;
		
		int rootA = find(a);
		int rootB = find(b);
		if(rootA == rootB) continue;
		
		sum += cost;
		
		if(rootA > rootB) root[a] = rootB;
		else root[b] = rootA;
	}
	return sum;
}
int main()
{
	scanf("%d %d", &N, &M);
	int a, b, cost;
	for(int i=0; i<=M; i++)
	{
		scanf("%d %d %d", &a, &b, &cost);
		e.push_back({a, b, !cost});
	}
	long long s1 = process(compare1);
	long long s2 = process(compare2);
	printf("%lld", s2*s2-s1*s1);
}

haja 7년 전 1

if(rootA > rootB) root[a] = rootB;

else root[b] = rootA;

이거를 root[rootA] = rootB
이렇게 바꿔보세요.

moonsoo5522 7년 전 0

어처구니 없는 실수를 했네요 ㅎㅎ 감사합니다.

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

문제

문제

출처

ICPC

13418 학교 탐방하기 문제 질문입니다.

moonsoo5522 7년 전 0

haja 7년 전 1

moonsoo5522 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말