글 읽기 - 무한루프는 시간초과에요 런타임 에러에요??

sksdong1 7년 전 0

MCMF로 짯는데 시간초과가 뜨는데. 최적화 문제일까요? 코딩 잘못한 부분이 있나요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;

class Main{
	final int MAX=1004,INF=987654321,SOURCE=0,SINK=1,A=2,B=3;
	int n,a,b;
	int[][] cap,flow,cost;

	Scanner sc = new Scanner(System.in);
	void solve()
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {

			while(true){
				StringTokenizer st = new StringTokenizer(br.readLine().trim());
				n = Integer.parseInt(st.nextToken());
				a = Integer.parseInt(st.nextToken());
				b = Integer.parseInt(st.nextToken());
				if(n==0 && a==0 && b==0) return;

				cap = new int[MAX][MAX];
				flow = new int[MAX][MAX];
				cost = new int[MAX][MAX];

				cap[SOURCE][A]=a;
				cap[SOURCE][B]=b;
				for(int idx=0;idx<n;idx++){
					st = new StringTokenizer(br.readLine().trim());
					int k = Integer.parseInt(st.nextToken());
					int d1 = Integer.parseInt(st.nextToken());
					int d2 = Integer.parseInt(st.nextToken());

					cap[A][4+idx] = k;
					cap[B][4+idx] = k;
					cost[A][4+idx] = d1;
					cost[B][4+idx] = d2;
					cost[4+idx][A] = -d1;
					cost[4+idx][B] = -d2;
					cap[4+idx][SINK] = k;
				}
				int ans =MCMF();
				System.out.println(ans);
			}
		}catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	int MCMF(){
		int total=0;
		boolean[] chk = new boolean[MAX];
		int[] dist = new int[MAX];
		int[] parent = new int[MAX];
		LinkedList<Integer> q = new LinkedList<Integer>();
		while(true){
			Arrays.fill(chk, false);
			Arrays.fill(dist, INF);
			Arrays.fill(parent, -1);
			dist[SOURCE]=0;
			parent[SOURCE]=SOURCE;
			q.clear();q.add(SOURCE);
			
			while(!q.isEmpty()){
				int u = q.poll();
				chk[u]=false;
				for(int v=0;v<MAX;v++){
					if(cap[u][v]-flow[u][v]>0 && dist[u]+cost[u][v]<dist[v]){
						dist[v] = dist[u]+cost[u][v];
						parent[v]=u;
						if(!chk[v]) {
							if(q.isEmpty()) q.add(v);
							else{
								if(dist[q.get(0)]>dist[v]) q.addFirst(v);
								else q.add(v);
							}
						}
						chk[v]=true;
					}
				}
			}
			if(parent[SINK]==-1) break;
			if(dist[SINK]<0) break;

			int ret = INF;
			for(int p=SINK;p!=SOURCE;p=parent[p]){
				ret = min(ret,cap[parent[p]][p] - flow[parent[p]][p]);
			}
			for(int p=SINK;p!=SOURCE;p=parent[p]){
				flow[parent[p]][p] += ret;
				flow[p][parent[p]] -= ret;
			}

			total += dist[SINK]*ret;

		}
		return total;
	}
	int min(int a,int b){
		return a>b?b:a;
	}
	public static void main(String[] args) {
		new Main().solve();
	}
}

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

문제

문제

출처

ICPC

무한루프는 시간초과에요 런타임 에러에요??

sksdong1 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말