백준 2316번: 도시 왕복하기 2 (Java)

https://www.acmicpc.net/problem/2316

2316번: 도시 왕복하기 2

 

 

 

 

 

 

 

 

---

 

풀이

라이님 블로그를 참고했습니다.

점을 한 번만 표현하기 위해, '정점 분할'을 해줍니다: 점 U를 점 U, U'으로 나누어, 점 U와 U' 사이 유량이 1인 단방향 간선으로 연결합니다.

점 U에서 점 V로 가는 양방향 간선을 다음과 같이 표현합니다: U'->V 단방향 간선, V'->U 단방향 간선

이후 에드몬드-카프 알고리즘을 수행하면 됩니다.

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int N;
    static List<List<Integer>> graph;
    static int[][] capacity, flow;
    static int[] parent;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());
        capacity = new int[2*N+1][2*N+1];
        flow = new int[2*N+1][2*N+1];
        graph = new ArrayList<>();
        for (int i = 0; i <= 2*N; i++) {
            graph.add(new ArrayList<Integer>());
        }
        // i번째 점: 2*i-1, 2*i에 대응 
        for (int i = 0; i < P; i++) {
            st = new StringTokenizer(br.readLine());
            int from = 2*Integer.parseInt(st.nextToken())-1;
            int to = 2*Integer.parseInt(st.nextToken())-1;
            graph.get(from).add(from+1);
            graph.get(from+1).add(from);
            graph.get(from+1).add(to);
            graph.get(to).add(from+1);
            graph.get(to).add(to+1);
            graph.get(to+1).add(to);
            graph.get(to+1).add(from);
            graph.get(from).add(to+1);
            capacity[from][from+1] = 1;
            capacity[from+1][to]++;
            capacity[to][to+1] = 1;
            capacity[to+1][from]++;
        }
        // 1, 2번 점은 두 번 이상 방문 
        System.out.println(maximumFlow(2, 3));
    }
 
    static int maximumFlow(int source, int sink) {
        int maxFlow = 0;
        while (true) {
            parent = new int[2*N+1];
            parent[source] = source;
            Queue<Integer> queue = new ArrayDeque<>();
            queue.offer(source);
            while (!queue.isEmpty() && parent[sink] == 0) {
                int cur = queue.poll();
                for (int nxt: graph.get(cur)) {
                    if (parent[nxt] == 0 && capacity[cur][nxt] - flow[cur][nxt] > 0) {
                        parent[nxt] = cur;
                        queue.offer(nxt);
                    }
                }
            }
            
            if (parent[sink] == 0) break;
            
            int tempFlow = Integer.MAX_VALUE;
            for (int cur = sink; cur != source; cur = parent[cur]) {
                tempFlow = Math.min(tempFlow, capacity[parent[cur]][cur] - flow[parent[cur]][cur]);
            }
            for (int cur = sink; cur != source; cur = parent[cur]) {
                flow[parent[cur]][cur] += tempFlow;
                flow[cur][parent[cur]] -= tempFlow;
            }
            maxFlow += tempFlow;
        }
        return maxFlow;
    }
}