글 읽기 - 위상정렬까지사용했는데.. 왜 런타임에러가 날까요...?

pose2done 6년 전 0

제가 dfs랑 dp를 사용하였고, Overflow피하려고 위상정렬도 사용하였는데

자꾸 4퍼센트에서 런타임에러가 나네요,,, 혼자 만들어본 간선 100개가 넘는 상황도 만들었는데 잘 되는데 어디가 문제일까요

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.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	private static ArrayList<Integer>[] child;
	private static ArrayList<Integer>[] parents;
	private static int[][] adjacentCost;
	private static int[] cave;
	private static Cave[] dp;
	private static int degree[];
	
	public static void main(String args[])throws IOException, CloneNotSupportedException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = Integer.parseInt(br.readLine());
		
		for(int t = 0; t<tc; t++){
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int n = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			
			child = new ArrayList[n+1];
			parents = new ArrayList[n+1];
			for(int i = 0; i<n+1; i++){
				child[i] = new ArrayList<>();
				parents[i] = new ArrayList<>();
			}
			adjacentCost = new int[n+1][n+1];
			
			st = new StringTokenizer(br.readLine());
			
			cave = new int[n+1];
			degree = new int[n+1];
			
			for(int i = 1;i<n+1;i++){
				cave[i] = Integer.parseInt(st.nextToken());
			}
			
			for(int i = 0; i<e; i++){
				st = new StringTokenizer(br.readLine());
				
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				int cost = Integer.parseInt(st.nextToken());
				
				child[from].add(to);
				parents[to].add(from);
				adjacentCost[from][to] = cost;
				degree[from]++;
			}
			
			dp = new Cave[n+1];
			Queue<Integer> readyQ = new LinkedList<>();
			
			for(int i =1; i<n+1;i++) {
				if(degree[i] == 0) readyQ.offer(i);
			}
			
			while(!readyQ.isEmpty()) {
				int tmp = readyQ.poll();
				degree[tmp]--;
				dfs(tmp);
				for(int x : parents[tmp]) {
					degree[x]--;
					if(degree[x] == 0) readyQ.offer(x);
				}
				
			}
			
			Cave resultCave = dfs(1);
			
			System.out.println(resultCave.cost + " " + resultCave.order.size());
			for(int i = resultCave.order.size()-1; i>=0; i--){
				System.out.print(resultCave.order.get(i)+ " ");
			}
			System.out.println();
			
		}
		
	}
	public static Cave dfs(int vertex) throws CloneNotSupportedException{
		
		if(dp[vertex] != null) return (Cave)dp[vertex].clone();
		
		ArrayList tmpArray = new ArrayList<>();
//		tmpArray.add(vertex);
		
		ArrayList<Cave> caves = new ArrayList<>();
		caves.add(new Cave(vertex,cave[vertex],tmpArray));
		
		for(int x : child[vertex]){
			Cave tmpCave = dfs(x);
			tmpCave.cost += cave[vertex] - adjacentCost[vertex][x];
			caves.add((Cave)tmpCave.clone());
		}
		
		Cave tmpCave = Collections.max(caves);
		tmpCave.order.add(vertex);
		
		return dp[vertex] = tmpCave;
		
	}
	
	static class Cave implements Comparable<Cave>,Cloneable{
		int vertex;
		int cost;
		ArrayList<Integer> order;
		public Cave(int vertex, int cost, ArrayList<Integer> order) {
			super();
			this.vertex = vertex;
			this.cost = cost;
			this.order = order;
		}
		@Override
		public int compareTo(Cave o) {
			// TODO Auto-generated method stub
			return this.cost - o.cost;
		}
		@Override
		protected Object clone() throws CloneNotSupportedException {
			// TODO Auto-generated method stub
			Cave clone = (Cave)super.clone();
			clone.cost = this.cost;
			clone.vertex = this.vertex;
			clone.order = (ArrayList<Integer>)this.order.clone();
			return clone;
		}
		
	}
}

bupjae 6년 전 1

adjacentCost 배열의 최대 크기는 10001 * 10001 * 4 = 약 381MB로 문제에서 주어진 제한 256MB를 넘어갑니다.

그래프를 저장할 다른 자료구조를 생각하셔야 합니다.

pose2done 6년 전 0

감사합니다! 아... 이거 자꾸 힙영역의 크기를 무시하고 코딩을하네요,

잘배워갑니다

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

문제

문제

출처

ICPC

위상정렬까지사용했는데.. 왜 런타임에러가 날까요...?

pose2done 6년 전 0

bupjae 6년 전 1

pose2done 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말