BOJ - 6086 ) 최대 유량

---

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

6086번: 최대 유량

---

주말동안의 PS주제는 포드-풀커슨알고리즘과 이분 매칭이였다.

 

https://coderkoo.tistory.com/4

네트워크플로우(Network flow) - 포드 풀커슨(Ford-Fulkerson) 알고리즘

최대유량은 네트워크에서 얼만큼 많이 유량을 흘려보낼수있는지를 계산하는 문제이다.

 

여태까지 최단경로로 A->B의 집합간 거리를 계산했다면,

 

이제는 최대로 많이 보내는 경우에 초점을 맞추어서 계산한다. 

 

그중 구현이 쉬운 포드-풀커슨알고리즘은 한 경로를 

 

A->B로 가는 한 경로를 선택하여 그 경로의 최소유량을 계속 흘려보냄과 동시에, 반대 방향에는

 

음의 유량이 있다고 가정하며 진행하는 알고리즘이다. 

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {
	private static int size = 702;
	public static void main(String[] args) throws Exception {
		//포드 풀커슨 알고리즘
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		
		int Capacity[][] = new int[size][size];
		for(int i = 0 ; i < n ; i ++) {
			st = new StringTokenizer(br.readLine());
			int s = st.nextToken().charAt(0) -'A';
			int e = st.nextToken().charAt(0) -'A';
			int f = Integer.parseInt(st.nextToken());
			Capacity[s][e] += f;
			Capacity[e][s] += f;
		}
		
		// end of input
		System.out.println(networkflow('A'-'A','Z'-'A',Capacity));
	}

	private static int networkflow(int start, int end, int[][] capacity) {
		
		int size = capacity.length;
		// a->b에서 정방향이면 b->a의 역방향의 -유량을 표시해준다.
		int flow[][] = new int[size][size];
		
		ArrayDeque<Integer> dq = new ArrayDeque<>();
		int res = 0;
		while(true) {
			dq.clear();
			int parent[] = new int[size];
			for(int i = 0 ; i < size ; i++) {parent[i] = -1;}
			dq.add(start); parent[start] = start;
			while(!dq.isEmpty() && parent[end] == -1) {
				int now = dq.poll();
				for(int i = 0 ; i < size ; i++) {
					if(capacity[now][i]-flow[now][i]>0 && parent[i]== -1) {
						// 연결되어서 유량을 보낼수 있는 경우 
						// 경로가 결정되지 않았을 경우
						dq.add(i);
						parent[i] = now;
					}
				}
			}
			
			
			if(parent[end]==-1) {
				break;
				// 유량경로가없으면 종료
			}
		
			// 한스텝에 얼마의 유량을 흘릴것인지?
			int flowamount = 2147000000;
			
			for(int s = end ; s != start ; s = parent[s]) {
				// 거꾸로 올라가면서 유량의 최솟값을 찾음
				flowamount = Math.min(flowamount, capacity[parent[s]][s] - flow[parent[s]][s]);
			}
			
			for(int s = end ; s!= start ; s = parent[s]) {
				// 부모 -> 자식으로 flowamount가 흐르면 자식->부모로 -flowamount가 흐른다.
				flow[parent[s]][s] +=flowamount;
				flow[s][parent[s]] -=flowamount;
			}
			res+=flowamount;
				
		}
		return res;
		
	}
}

---