• 굵은 점선으로 표시된 유량을 보내는 경로를 증가 경로라고 한다.
• 경로를 따라 유량을 보내려면 이미 흐르는 유량 외에 추가로 보낼 수 있는 여유 용량이 있어야 한다. 간선의 용량과 유량의 차이를 잔여 용량이라고 한다. 간선 용량 10인데 현재 유량이 6이면 4만큼 더 보낼 수 있는 거. r(u,v) = c(u,v) - f(u,v)

모든 간선의 유량을 0으로 두고 시작해, 소스에서 싱크로 유량을 더 보낼 수 있는 경로를 찾아 유량을 보내기를 반복한다.

근데 사진에서 문제가 만약, s→a→t가 아니라 s→a→b→t가 돼 버리면, 최대 유량을 찾을 수 없다. 어떻게 해결하는가?

⇒ b→a 간선은 없으므로 해당 간선의 용량 c(b,a)는 0이지만, 유량의 대칭성에 의하면 유량 f(b,a)는 -1이다. 그렇다면 b→a의 잔여 용량은 0 - (-1) 1이다. 실제로 존재하지 않는 간선으로 유량을 보낼 수 있는 것은 흘러오는 유량을 줄이는 것이 상대에게 유량을 보내주는 것과 같은 효과를 갖기 때문이다.

const int INF = (~0U >> 2);
int V;
// capacity[u][v] = u에서 v로 보낼 수 있는 용량
// flow[u][v] = u에서 v로 흘러가는 유량 (반대 방향인 경우 음수)
int capacity[MAX_V][MAX_V], flow[MAX_V][MAX_V];
// flow[][]를 계산하고 총 유량을 반환한다.
int networkFlow(int source, int sink)
{
	// flow를 0으로 초기화한다.
	memset(flow, 0, sizeof(flow));
	int totalFlow = 0;
	while (true)
	{
		//너비 우선 탐색으로 증가 경로를 찾는다.
		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;
}

우선 잔여 용량이 남아 있는 간선만을 이용해 너비 우선 탐색을 수행.

소스에서 싱크까지의 경로를 찾아냈다면 각 간선을 검사하면서 그중 최소 잔여 용량을 찾는다. 이것이 이 경로를 따라 보낼 수 있는 최대 유량이다.

그 후에는 각 간선의 유량을 갱신하는데, 유량의 대칭성을 유지하기 위해 한 방향의 유량을 늘리면 다른 방향의 유량은 줄인다.

시간복잡도

최대 유량 f에 대해 O(Ef)