네트워크 유량 ( 포드 풀커슨 )

포드 풀커슨 알고리즘은 네트워크 유량을 구하기 위한 문제이다. 특정 시작점에서 특정 끝점까지 한번에 보낼 수

최대 유량값을 찾는 문제이다.

 

구현 방법

 

bfs를 이용하여 시작점에서 끝점까지 탐색 ( 그 과정에서 자신으로 들어오는 부모 정점 저장 )

 

끝점부터 시작하여 해당 경로를 통해 옮길 수 있는 유량을 확인 ( 경로 중 가장 작은 값)

 

찾은 유량 값을 갱신 ( 반대 방향은 음수로 갱신)

 

이 것을 끝점에 닿는 증가경로가 없을 때까지 반복

 

const int INF = 99999999;
int V;

// capacity[u][v] : u에서 v로 보낼 수 있는 용량
// flow[u][v] : u에서 v로 보낸 유량 ( 반대 방향일 경우 음수 )
int capacity[MAX_V][MAX_V];
int flow[MAX_V][MAX_V];

// flow를 계산하고 총 유량을 반환
int networkFlow(int source, int sink) {
	memset(flow, 0, sizeof(flow));

	int totalFlow = 0;

	while (true) {
		// bfs로 증가경로 탐색
		vector<int> parent(MAX_V, -1);
		queue<int> q;
		parent[source] = source;
		q.push(source);

		while (!q.empty() && parent[sink] == -1) {
			int here = q.front();
			q.pop();

			for (int there = 0; there < V; there++) {
				if (capacity[here][there] - flow[here][there] > 0 && parent[there] == -1) {
					q.push(there);
					parent[there] = here;
				}
			}
		}

		//증가경로가 없으면 종료
		if (parent[sink] == -1) {
			break;
		}

		int amount = INF;

		for (int p = sink; p != source; p = parent[p]) {
			amount = min(capacity[parent[p]][p] - flow[parent[p][p], amount);
		}

		// 증가경로를 통해 유량을 보낸다
		for (int p = sink; p != source; p = parent[p]) {
			flow[parent[p]][p] += amount;
			flow[p][parent[p]] -= amount;
		}
		totalFlow += amount;
	}
	return totalFlow;
}