글 읽기 - 메모리초과 왜 때문이죠..?

tmdwkd2 3년 전 0

문제가 무엇인지 도무지 모르겠습니다..

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	static int n, m;
	static int p[];
	static int line;

	static class point implements Comparable<point> {
		int y;
		int x;
		int weight;
		public point(int y, int x, int weight) {
			super();
			this.y = y;
			this.x = x;
			this.weight = weight;
		}
		@Override
		public int compareTo(point o) {
			// TODO Auto-generated method stub
			return Integer.compare(this.weight, o.weight);
		}
	}
	static PriorityQueue<point> pq;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		p = new int[n+1];
		pq = new PriorityQueue<>();
		for (int i = 1; i < n+1; i++) {
			p[i] = i;
		}
		for (int i = 0; i < m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			union(a, b);
			line++;
		}
		int w;
		for (int i = 1; i < n+1; i++) {
			for (int j = 1; j < n+1; j++) {
				w = sc.nextInt();
				if(i < j) {
					pq.offer(new point(i, j, w));
				}
			}
		}
		int cnt = 0;
		int sum = 0;
		ArrayList<int[]> ans = new ArrayList<>();
		while (!pq.isEmpty()) {
			point cur = pq.poll();
			if (cur.y == 1 || cur.x == 1)	continue;
			if (union(cur.y, cur.x)) {
				cnt++;
				sum += cur.weight;
				ans.add(new int[] { cur.y, cur.x });
				line++;
			}
			// mst로 연결된 간선의 갯수가 1번 정점빼고 다 연결됨
			if (line == n - 2)
				break;
		}
		System.out.println(sum + " " + cnt);
		for (int[] is : ans) {
			System.out.println(is[0] + " " + is[1]);
		}
	}

	private static boolean union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a == b) {
			return false;
		}
		if (a < b) {
			p[b] = a;
			return true;
		} else {
			p[a] = b;
			return true;
		}
	}

	private static int find(int x) {
		// TODO Auto-generated method stub
		if (p[x] == x)
			return x;
		return p[x] = find(p[x]);
	}
}

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

문제

문제

출처

ICPC

메모리초과 왜 때문이죠..?

tmdwkd2 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말