글 읽기 - 자바(에드먼드 카프 알고리즘)로는 풀 수 없는건가요?

yumk0717 2년 전 0

에드먼드 카프 이용하고

스타트와 싱크 말고 따로 브릿지를 줘서 벌점에 해당하는 플로우는 그쪽으로 흐르게 해놨는데

답은 맞게 나오는거 같은데

시간 초과가 되네요

자바로는 한계가 있는 건가요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());
		int k=Integer.parseInt(st.nextToken());
		int start=0;
		int sink=2001;
		int bridge=2002;
		c=new int[2003][2003];
		f=new int[2003][2003];
	for(int i=0;i<=2003;i++) {
		graph.add(new ArrayList<Integer>());
	}	
	for(int i=1;i<=n;i++) {
		graph.get(start).add(i);
		graph.get(i).add(start);
		c[start][i]=1;
		graph.get(bridge).add(i);
		graph.get(i).add(bridge);
		c[bridge][i]=k;
	}
	for(int i=1001;i<=1000+m;i++) {
		graph.get(sink).add(i);
		graph.get(i).add(sink);
		c[i][sink]=1;
	}
	graph.get(start).add(bridge);
	graph.get(bridge).add(start);
	c[start][bridge]=k;
	
	
	for(int i=1;i<=n;i++) {
		st=new StringTokenizer(br.readLine());
		int a=Integer.parseInt(st.nextToken());
		for(int j=1;j<=a;j++) {
			int work=Integer.parseInt(st.nextToken())+1000;
			graph.get(i).add(work);
			graph.get(work).add(i);
			c[i][work]=1;
		}
	}
	maxflow(start,sink);
		
	System.out.println(result);
	
	}
static int INF=10000000;
static ArrayList<ArrayList<Integer>> graph=new ArrayList<>();
static int[][] c;
static int[][] f;
static int[] d=new int[2003];
static int result;
static void maxflow(int start, int sink) {
		while(true) {
			Arrays.fill(d,-1);
			Queue<Integer> q=new LinkedList<>();
			q.offer(start);
			while(!q.isEmpty()) {
				int x=q.poll();
				for(int y:graph.get(x)) {
					if(c[x][y]-f[x][y]>0&&d[y]==-1) {
						d[y]=x;
						q.offer(y);
						if(y==sink) {break;}
					}
				}
				
			}
			if(d[sink]==-1) {break;}
			int flow=INF;
			for(int i=sink;i!=start;i=d[i]) {
				flow=Math.min(flow,c[d[i]][i]-f[d[i]][i]);
			}
			for(int i=sink;i!=start;i=d[i]) {
				f[d[i]][i]+=flow;
				f[i][d[i]]-=flow;
			}
			result+=flow;
		}
}//////에드몬드 카프 알고리;즘
	
}

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

문제

문제

출처

ICPC

자바(에드먼드 카프 알고리즘)로는 풀 수 없는건가요?

yumk0717 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말