글 읽기 - 에드몬드-카프는 통과하는데 디닉은 시간초과가 뜨네요???

reperdof 1년 전 0

디닉으로 문제를 푸는데 계속 시간초과가 뜨길래 한참 코드를 바꿔보며 고민하다가 한번 에드몬드-카프로 제출해봤더니 통과하네요.

다른 문제는 디닉으로 잘 통과해서 코드에는 문제가 없는 것 같은데...

뭐가 문제일까요?

코드 첨부합니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
import java.math.*;
import java.text.DecimalFormat;

public class Main {
	
	static int[][] flow; // flow : 유량 그래프
	static ArrayList<int[]>[] leg, gr; // leg : 레벨그래프, gr : 용량 그래프
	static int n, m, N, st = 0, en = 1, sums; // st : source, en : sink
	static boolean end; // 추가적인 유량이 더 흐를 수 없을 경우 true
	static final int inf = 1000000000;
	
	public static void main(String[] args) throws IOException {
		BufferedReader rr = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter ww = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(rr.readLine());
		for (int z = 0; z < T; z++) {
			String[] s = rr.readLine().split(" ");
			n = Integer.parseInt(s[0]); m = Integer.parseInt(s[1]);
			N = n*m+2; sums = 0;
			gr = new ArrayList[N];
			flow = new int[N][N];
			for (int i = 0; i < N; i++) gr[i] = new ArrayList<>();
			for (int i = 0; i < n; i++) {
				s = rr.readLine().split(" ");
				boolean odd = (i % 2 == 1) ? true : false;
				for (int j = 0; j < m; j++) {
					int c = Integer.parseInt(s[j]);
					sums += c;
					int cn = i*m+j+2; // 현재 노드의 index
					if (odd) {
						av(st, cn, c); // source -> 홀수 노드
						ade(i-1, j, cn); ade(i+1, j, cn); // 홀수 노드 -> 짝수 노드
						ade(i, j-1, cn); ade(i, j+1, cn);
					} else av(cn, en, c); // 짝수 노드 -> sink
					odd = !odd;
				}
			}
			end = false;
			while (true) {
				bfs(); // 에드몬드-카프 알고리즘
                //tam(); // 디닉 알고리즘
				if (end) break;
			}
			for (int i = 0; i < N; i++) sums -= flow[st][i];
			ww.write(sums + "\n");
		}	
		ww.flush();
		ww.close();
	}
	
	static void ade(int i, int j, int cn) {
		if (i < 0 || j < 0 || i >= n || j >= m) return; // 간선 추가가 가능한 방향인지 확인
		int dn = i*m+j+2;
		av(cn, dn, inf);
	}
	
	static void av(int i, int j, int k) { // 용량 그래프에 간선 추가
		int[] c1 = {j, k}, c2 = {i, 0}; // {연결된 노드, 용량}
		gr[i].add(c1); gr[j].add(c2);
	}
	
	static void tam() { // 디닉
		leg = new ArrayList[N];
		for (int i = 0; i < N; i++) leg[i] = new ArrayList<>(); // 레벨그래프 생성
		ArrayDeque<Integer> q = new ArrayDeque<>(); // 큐 생성
		int[] lev = new int[N]; // 각 노드의 level 저장
		int f = st, level = 1; // f : 현재 노드, level : 현재 노드의 레벨
		lev[f] = level;
		boolean isP = false; // sink에 도달 가능시 true
		while (true) {
			level++;
			for (int[] cur : gr[f]) {
				int clv = lev[cur[0]]; // f와 연결된 노드(cur[0])의 레벨(탐색된 적이 없으면 0)
				if (clv != 0 && clv != level || cur[1] - flow[f][cur[0]] <= 0) continue;
                // clv가 (f의 레벨)+1이 아니면 continue, 용량이 남아 있지 않으면 continue
				leg[f].add(cur); // 레벨그래프에 간선 추가
				if (clv != 0) continue; // cur[0]가 탐색되었으면 continue;
				lev[cur[0]] = level; // cur[0]의 레벨 저장
				q.add(cur[0]); // 큐에 다음 탐색 노드 저장
				if (cur[0] == en) isP = true; // sink에 도달 가능시 true
			}
			if (q.isEmpty()) break;
			f = q.pollFirst(); // 다음 탐색 노드
			level = lev[f];
		}
		if (!isP) {
			end = true;
			return;
		}
		dfs(st, inf); // 레벨그래프를 dfs로 탐색
	}
	
	static int dfs(int i, int j) { // 디닉에서 레벨그래프 탐색 (i : 현재 노드, j : 현재 노드로 들어올 수 있는 최대 유량)
		if (i == en) return j;
		int sum = 0; // i에서 보내는 유량의 합
		for (int[] c : leg[i]) {
			int r = dfs(c[0], Math.min(j, c[1] - flow[i][c[0]])); // i와 연결된 노드의 탐색
			if (r > 0) {
				flow[i][c[0]] += r; // 유량 추가
				flow[c[0]][i] -= r;
				j -= r;
				sum += r;
				if (j <= 0) break;
			}
		}
		return sum;
	}
	
	static void bfs() { // 에드몬드-카프
		int f = st;
		int[] p = new int[N], pc = new int[N]; // p : 이전 노드, pc : 이전 노드와 현 노드 사이의 용량
		Arrays.fill(p, -1);
		ArrayDeque<Integer> q = new ArrayDeque<>();
		while (true) {
			for (int[] c : gr[f]) {
				if (p[c[0]] != -1 || c[1] - flow[f][c[0]] <= 0) continue;
				p[c[0]] = f; pc[c[0]] = c[1];
				if (c[0] == en) {
					int pf = f, ef = en;
					ArrayDeque<int[]> ln = new ArrayDeque<>();
					int min = inf;
					while (true) {
						if (pc[ef] - flow[pf][ef] < min) min = pc[ef] - flow[pf][ef];
						int[] cc = {pf, ef};
						if (pf == st) {
							while (true) {
								flow[pf][ef] += min;
								flow[ef][pf] = -flow[pf][ef];
								if (ln.isEmpty()) break;
								int[] co = ln.pollFirst();
								pf = co[0]; ef = co[1];
							}
							return;
						}
						ln.add(cc);
						ef = pf; pf = p[pf];
					}
				}
				q.add(c[0]);
			}
			if (q.isEmpty()) break;
			f = q.pollFirst();
		}
		end = true;
	}
}

reperdof 1년 전 0

다른 문제 풀다가 해결했네요.

dfs 부분에서 102~103처럼 코드를 짜면 중복 탐색하는 경우가 생길 수 있네요.

다른 문제에서는 입력이 널널에서 문제가 없었던 거군요.

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

문제

문제

출처

ICPC

에드몬드-카프는 통과하는데 디닉은 시간초과가 뜨네요???

reperdof 1년 전 0

reperdof 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말