글 읽기 - 프림 알고리즘 반례를 모르겠어요 ㅠㅜㅜ

terec 2년 전 0

프림 알고리즘으로 최소 신장 트리를 구성해서 구현해봤습니다

오버플로우가 안나게 double 로도 잘 바꿔준 것 같은데 54% 쯤에서 자꾸자꾸자꾸 틀리네요 ㅠㅠ

틀린점 지적해주시거나 반례 알려주시면 매우매우 감사하겠습니다ㅠㅜㅠ

import java.io.*;
import java.util.*;

public class Main {
	private static double[][] arr;
	private static double[] min;
	private static int N;
	private static int M;

	public static void main(String[] args) throws IOException{
		init();
		System.out.printf("%.2f", solve(0));
	}

	private static void init() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		int[][] gods = new int[N][2];
		arr = new double[N][N];
		min = new double[N];

		for (int i = 0; i < N ; i++) {
			st = new StringTokenizer(br.readLine());
			gods[i][0] = Integer.parseInt(st.nextToken());
			gods[i][1] = Integer.parseInt(st.nextToken());
			min[i] = Double.MAX_VALUE;
		}

		for (int i = 0; i < N ; i++) {
			for (int j = i + 1; j < N ; j++) {
				arr[j][i] = arr[i][j] = getDist(gods[i], gods[j]);
			}
		}

		for (int i = 0; i < M ; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken()) - 1;
			int to = Integer.parseInt(st.nextToken()) - 1;
			arr[from][to] = 0;
			arr[to][from] = 0;
		}
	}

	private static double getDist(int[] x, int[] y) {
		double val1 = Math.pow((double) x[0] - (double) y[0], 2);
		double val2 = Math.pow((double) x[1] - (double) y[1], 2);

		return Math.sqrt(val1 + val2);
	}

	private static double solve(int start) {
		final int IDX = 0;
		final int VAL = 1;
		boolean[] visited = new boolean[N];

		Queue<Object[]> pq = new PriorityQueue<>((o1, o2) -> (int)((double)o1[VAL] - (double)o2[VAL]));
		min[start] = 0;
		pq.offer(new Object[]{start, 0.0});

		double ret = 0;
		for (int i = 0; i < N ; i++) {
			Object[] cur;
			do{
				cur = pq.poll();
			} while(visited[(int)cur[IDX]]);

			int idx = (int)cur[IDX];
			ret += (double)cur[VAL];
			visited[idx] = true;

			for (int j = 0; j < N ; j++) {
				if(visited[j] | min[j] <= arr[idx][j])  continue;
				min[j] = arr[idx][j];
				pq.offer(new Object[]{j, min[j]});
			}
		}
		return ret;
	}
}

terec 2년 전 2

자문자답합니다 ..ㅠㅠ

Comapartor를 제대로 구현하지 않아서 발생한 문제였어요. double의 크기 비교를 int로 반환하니까 같은 정수값을 가진 값끼리는 비교가 제대로 안되었습니다.

//잘못된 comparator
Queue<Object[]> pq = new PriorityQueue<>((o1, o2) -> (int)((double)o1[VAL] - (double)o2[VAL]));

//변경 후
Queue<Object[]> pq = new PriorityQueue<>(Comparator.comparingDouble(o -> (double) o[VAL]));

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

문제

문제

출처

ICPC

프림 알고리즘 반례를 모르겠어요 ㅠㅜㅜ

terec 2년 전 0

terec 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말