글 읽기 - 에드몬드카프 알고리즘으로는 Ac 받을수 없는건가요 ..?

wldn4444 4년 전 0

제 코드에서 시간을 더 줄일수 잇는 요소가 있는지 궁금합니다...

혹시 에드몬드카프알고리즘으로는 AC받을수없고,,

이분매칭으로 풀어야할까요?

약 69%정도에서 시간초과가 나고 있습니다. ..

유량관련문제를.. 공부중이라 염치없이 문의드립니다..

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

public class Main {
	public static int[][] c;
	public static int[][] f;
	public static int N,M;
	public static int MAX_N = 1000;
	public static int MAX_NM = 1000*2+2;
	public static ArrayList<ArrayList<Integer>> adj;
	public static void main(String[] args) throws IOException {

		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		c = new int[MAX_NM][MAX_NM]; f = new int[MAX_NM][MAX_NM];
		adj = new ArrayList();
		for(int i=0; i<MAX_NM; i++) {
			adj.add(new ArrayList());
		}
		int source = MAX_NM-2; int sink = MAX_NM-1;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int k = Integer.parseInt(st.nextToken());
			for(int j=0; j<k; j++) {
				int node = Integer.parseInt(st.nextToken())+MAX_N-1;
				//직원 -> 일 모델링
				adj.get(i).add(node);
				adj.get(node).add(i);
				c[i][node] = 1;
			}
			//source ->직원
			adj.get(source).add(i);
			adj.get(i).add(source);
			c[source][i] = 1;
		}
		//직원 -> sink
		for(int i=MAX_N; i<MAX_N+M; i++) {
			adj.get(i).add(sink);
			adj.get(sink).add(i);
			c[i][sink] = 1;
		}
		int answer = 0;
		while(true) {
			
			int[] prev = new int[MAX_NM];
			Arrays.fill(prev, -1);
			Queue<Integer> que = new LinkedList<Integer>();
			que.add(source);
			prev[source] = source;
			while(!que.isEmpty()&& prev[sink]==-1) {
				int curr = que.poll();
				for(int next : adj.get(curr)) {
					if(c[curr][next]-f[curr][next]>0 && prev[next]==-1) {
						prev[next] = curr;
						que.add(next);
					}
					if(next==sink) break;
				}
			}
			//증가경로가 없으면
			if(prev[sink]==-1) break;
			int max_Flow = 1;
			
			for(int i=sink; i!=source; i=prev[i]) {
				f[prev[i]][i] += max_Flow;
				f[i][prev[i]] -= max_Flow;
			}
			answer+= max_Flow;
		}
		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}


}

jinhan814 3년 전 0

c++로 에드몬드-카프 알고리즘을 구현해서 풀었더니 1964ms로 아슬아슬하게 통과됐습니다. 이분매칭으로 푸는게 맞는 문제인 거 같네요..

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

문제

문제

출처

ICPC

에드몬드카프 알고리즘으로는 Ac 받을수 없는건가요 ..?

wldn4444 4년 전 0

jinhan814 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말