글 읽기 - 13418번 학교 탐방하기 문제 자꾸 틀립니다.

kks227 7년 전 0

최소 스패닝 트리와 최대 스패닝 트리의 cost를 구해서 푸는 문제가 아닌가요?

뭔가 사소한 실수가 있는 것일까요...

N, M이 입력보다 실제로 1 많다는 것도 처리했는데...

문제에서 "필요한 최소한의" 경로만 사용한다고 했으므로 최악의 경우도 스패닝 트리는 맞을 텐데...

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

// 간선 구조체
struct Edge{
	int u, v, w;
	Edge(): Edge(-1, -1, 0){}
	Edge(int u1, int v1, int w1): u(u1), v(v1), w(w1){}
	// 가중치 순으로 정렬
	bool operator <(const Edge &O)const{ return w < O.w; }
};

// 유니온 파인드 배열: 음수면 root
int uf[1001];

// find 연산
int uf_find(int n){
	if(uf[n] < 0) return n;
	return uf[n] = uf_find(uf[n]);
}

// union 연산
bool uf_union(int a, int b){
	a = uf_find(a);
	b = uf_find(b);
	if(a == b) return false;
	uf[b] = a;
	return true;
}



int main(){
	int N, M, r1 = 0, r2 = 0;
	Edge e[1000000];
	scanf("%d %d", &N, &M);
	// 실제로 정점, 간선 개수 1 더 많음
	N++; M++;
	// 간선 정보 입력받고 정렬
	for(int i=0; i<M; i++){
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		e[i] = Edge(u, v, w);
	}
	sort(e, e+M);

	// 최소 스패닝 트리 cost 구하기
	fill(uf, uf+N, -1);
	for(int i=0; i<M; i++)
		if(uf_union(e[i].u, e[i].v)) r1 += e[i].w;
	// 최대 스패닝 트리 cost 구하기
	fill(uf, uf+N, -1);
	for(int i=M-1; i>=0; i--)
		if(uf_union(e[i].u, e[i].v)) r2 += e[i].w;
	// 정답 출력
	printf("%d\n", r2*r2 - r1*r1);
}

alohajihwan 7년 전 3

문제를 잘 읽어 보시면 w 가 0일때 오르막길 입니다. 따라서 구조체 sort할 때 w > O.w 로 고쳐 주어야 하며

r1 += (e[i].w == 0) 으로 수정해주면 맞았습니다가 뜹니다.

kks227 7년 전 0

감사합니다. 그냥 오름차순 정렬하고 cost를 그대로 더하면 될 줄 알았는데 예제만 되는 거였군요.

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

문제

문제

출처

ICPC

13418번 학교 탐방하기 문제 자꾸 틀립니다.

kks227 7년 전 0

alohajihwan 7년 전 3

kks227 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말