글 읽기 - mcmf 시간초과 질문입니다.

sksdong1 7년 전 0

그래프 모델링을

Source -> 직업 -> 사람 -> SINK, 이런식으로 했는데요,

50%에서 시간초과가 나는데 알고리즘이 문제인지 아니면 인접리스트로 바꾸면 AC 받나요??

아직 인접리스트로 짜는걸 안해봐서. 인접리스트로 AC받는거면 공부를 해서 풀겠습니다..

아니면 알고리즘에 문제가 있는지요.

유량도 어차피 한사람당 한개씩 매칭되니까 1씩밖에 못올려서 m번 탐색 다 해야될텐데. 다른 부분이 뭐가 문제가 있을까요??

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

class Main{

	final int SINK=1,SOURCE=0,INF=987654321;
	int n,m,MAX;
	int[][] cap,cost,flow;
	int[][] satisfaction = {
			{4,3,2,1},{8,7,6,5},{12,11,10,9}
	};

	Scanner sc = new Scanner(System.in);
	void solve(){
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		while(true){
			try{
				StringTokenizer st = new StringTokenizer(br.readLine().trim());
				n = Integer.parseInt(st.nextToken());
				m = Integer.parseInt(st.nextToken());
				if(n==0 && m==0) break;
				MAX = 2+n+m;

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

				for(int i=0;i<n;i++){
					cap[SOURCE][2+i] = sc.nextInt();
				}
				for(int i=0;i<m;i++){
					int year = sc.nextInt();
					year--;
					for(int j=0;j<4;j++){
						int job = sc.nextInt();
						cap[2+job][2+n+i] = 1;
						cost[2+job][2+n+i] = satisfaction[year][j];
						cost[2+n+i][2+job] = -cost[2+job][2+n+i];
					}
				}

				for(int i=0;i<m;i++){
					cap[2+n+i][SINK]=1;
				}

				int ans = mcmf();
				bw.write(ans+"\n");
			}
			catch(Exception e){
				e.printStackTrace();
			}
		}
		try {
			bw.close();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	int mcmf(){
		int maxFlow=0;
		LinkedList<Integer> q = new LinkedList<Integer>();
		boolean[] chk = new boolean[MAX];
		int[] dist = new int[MAX];
		int[] parent = new int[MAX];
		while(true){
			Arrays.fill(chk,false);
			Arrays.fill(parent,-1);
			Arrays.fill(dist,-INF);
			dist[SOURCE]=0;
			parent[SOURCE]=SOURCE;
			q.add(SOURCE);
			while(!q.isEmpty()){
				int here = q.poll();
				chk[here]=false;
				for(int i=0;i<MAX;i++){
					if(cap[here][i]-flow[here][i]>0){
						if(dist[here]+cost[here][i]>dist[i]){
							dist[i] = dist[here]+cost[here][i];
							parent[i]=here;
							if(!chk[i]) q.add(i);
							chk[i]=true;
						}
					}
				}
			}

			if(parent[SINK]==-1) break;


			for(int p=SINK;p!=SOURCE;p=parent[p]){
				flow[parent[p]][p] += 1;
				flow[p][parent[p]] -= 1;
			}

			maxFlow += dist[SINK];
		}
		return maxFlow;

	}
	public static void main(String[] args) {
		new Main().solve();
	}
}

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

문제

문제

출처

ICPC

mcmf 시간초과 질문입니다.

sksdong1 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말