Ford - Fulkserson 최대 유량 알고리즘

 

Ford - Fulkerson 알고리즘은 3단계로 이루어져 있습니다.

 

1. 그래프 순회 알고리즘(DFS/BFS)을 이용해 Augmenting path 찾기
2. Augmenting path의 V1, V2, V3, ... , Vn 사이에 존재하는 residual capacity의 최소값 찾기.
3. residual capacity의 최소값만큼 Skew Symmetry 성질을 이용해 지나온 path상의 flow 들을 f(u,v)=-f(u,v)해줍니다.

이때 residual capacity는 capacity[u][v] - flow[u][v]이고 u,v 사이의 간선에 흐를 수 있는 유량의 양이라고 생각하면 됩니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#define INF 999999999

using namespace std;

int ford_fulkerson(int s, int t);
int dfs(int s, int t, int c);

vector<vector<int>> capacity, flow;
vector<bool> visit;


int ford_fulkerson(int s, int t) {
	int ans = 0, f;

	for (int i = 0; i <= t; i++) {
		visit[i] = false;
	}

	while ((f=dfs(s, t, INF)) != 0) {
		ans += f;

		for (int i = 0; i <= t; i++) {
			visit[i] = false;
		}
	}

	return ans;
}

int dfs(int s, int t, int c) {
	int f;
	if (visit[s]) {
		return 0;
	}
	visit[s] = true;
	if (s == t) {
		return c;
	}

	for (int i = 1; i <= t; i++) {
		if (capacity[s][i] > flow[s][i]) {
			f = dfs(i, t, min(c, capacity[s][i] - flow[s][i]));
			if (f != 0) {
				flow[s][i] += f;
				flow[i][s] -= f;
				return f;
			}
		}
	}
	return 0;
}

재귀의 filo 성질을 이용해 dfs를 만들고 재귀를 호출하면서 residual capacity의 최소값을 인자로 넘겨줍니다.

 

t에서 함수가 끝나고 이때 구한 residual capcaity를 반환합니다.

 

반환받은 residual capacity를 이용해 각 flow 간선에 + - 해주면 끝!! ㅋㅋ