글 읽기 - 전력난 문제.. 도저히 틀린 이유를 모르겠습니다.. ㅠㅠ

niceman4u 6년 전 0

안녕하세요.

6497번 전력난 문제를 풀어 보고 있는데, MST 알고리즘의 하나인 크루스칼 알고리즘으로 풀었습니다.

그런데, 제출을 하고 나면 50%정도 돌다가 "틀렸습니다." 하고 통과가 되지 않는데, 아무리 코드를 드려다 봐도

잘 못된 부분을 찾지를 못하겠네요..ㅠㅠ

어디가 틀렸는지 제발 알려 주시면 감사하겠습니다..ㅠㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

class Info {
	int X, Y;
	long W;
	
	Info (int X, int Y, long W) {
		this.X = X;
		this.Y = Y;
		this.W = W;
	}
}

public class Main {	
	
	public static int P[] = null;
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		
		P = new int[M+1];
		
		ArrayList<Info> Arr = new ArrayList<Info>();
		
		long TotalSum = 0, MST = 0;
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			
			int X = Integer.parseInt(st.nextToken());
			int Y = Integer.parseInt(st.nextToken());
			long W = Long.parseLong(st.nextToken());
			
			TotalSum += W;
			
			Arr.add(new Info(X, Y, W));
		}
		
		st = new StringTokenizer(br.readLine());
		st.nextToken();
		st.nextToken();
		
		Arrays.fill(P,  -1);
		
		Collections.sort(Arr, new Comparator<Info>() {
			public int compare(Info o1, Info o2) {
				if ( o1.W > o2.W) return 1;
				else if ( o1.W == o2.W ) return 0;
				else return -1;
				
			}
		});
		
		
		int cnt = 0;
		for (Info edge : Arr){
			if ( union(edge.X,edge.Y)) {
				MST += edge.W;
				
				++cnt;				
				if ( cnt == M - 1) break;
			}
		}
		
		System.out.println(TotalSum - MST);
		
	}
	
	public static int find(int n) {
		if ( P[n] < 0) {
			return n;
		}
		
		return P[n] = find(P[n]);
	}
	
	public static boolean union(int a, int b) {
		int x = find(a);
		int y = find(b);
		
		if ( x == y ) return false;
		
		P[x] = y;
		return true;
	}

}

sgchoi5 6년 전 1

Ulm Local Contest 문제는 대회에서 사용했던 TC 가 공개되어 있으니 써 보세요.

https://gooddaytocode.blogspot...

niceman4u 6년 전 8

에고.. 문제의 조건을 제대로 보지 못해서.. 틀렸네요..ㅠㅠ

백준의 다른 문제들 처럼 테스트 케이스가 하나뿐이라고 생각하고 풀어서... 결과가 틀린 거였습니다.

계속 문제의 조건을 제가 임의로 해석을 하는 경향이 있네요...ㅠㅠ

감사합니다.

--------------------------------------------------------------

입력은 여러 개의 테스트 케이스로 구분되어 있다.

각 테스트 케이스의 첫째 줄에는 집의 수 m과 길의 수 n이 주어진다. (1 ≤ m ≤ 200000, m-1 ≤ n ≤ 200000)

이어서 n개의 줄에 각 길에 대한 정보 x, y, z가 주어지는데, 이는 x번 집과 y번 집 사이에 양방향 도로가 있으며 그 거리가 z미터라는 뜻이다. (0 ≤ x, y < m, x ≠ y)

도시는 항상 연결 그래프의 형태이고(즉, 어떤 두 집을 골라도 서로 왕래할 수 있는 경로가 있다), 도시상의 모든 길의 거리 합은 231미터보다 작다.

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

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

문제

문제

출처

ICPC

전력난 문제.. 도저히 틀린 이유를 모르겠습니다.. ㅠㅠ

niceman4u 6년 전 0

sgchoi5 6년 전 1

niceman4u 6년 전 8

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말