네트워크 플로우

 네트워크 플로우의 기본 정의는 위키에 나와있듯,

 'In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge.'

즉, 유향 그래프이고 가중그래프 G 가 각각의 노드를 연결한 에지들의 유량을 통해서

문제를 모델링하는 과정인 셈이다.

실제로, 네트워크 플로우 문제는 직접 봐서는 네트워크플로우로 풀어야 하는건가? 라고 알 수 있을 만큼 직관적이지 않다.

(물론 내공이 쌓이면 다르겠지만.. 저같은 초보 알고리즘학습자에게는...ㅠㅠ)

우선 문제를 모델링하는 과정은 다음과 같다.

보통 네트워크 플로우 문제는 아래 그림과 같이 특정 작업에 대한 능력을 capacity로 나타내고 (용량)

해당 capacity를 통해 흘러보낼 수 있는 유량을 계산한다.

이 알고리즘의 경우 백준온라인저지의 문제를 예시삼아 설명해보도록 하겠다.

우선 네트워크플로우는 시작위치라 할 수 있는 Source와 종결지점이라 할 수 있는 Sink가 존재한다.

 1) Source에서 출발하여 Sink 까지 갈 수 있는 경로가 있는지 파악하고 난 후 

 2) DFS또는 BFS (Edmonds-Karp 알고리즘) 을 통해  parent에 저장 후 

 3) 다시 Sink에서 Source로 back tracking하면서 유량을 감소시킨다. 

이 과정을 계속 진행하다보면 더이상 갈 수 없는 경로가 생기고 종료한다.

배열을 만들 때 초기화해주는 과정이 중요한데, 2188의 문제를 예시로 들면 

 0은 Source, 

 1~N까지는 N마리의 소, 

 N+1~ N+M 까지는 M개의 축사, 

 Sink는 N+M+1이 된다.

자세한 사항은 아래의 그림을 통해 나타내보도록 하겠다. 

2188 축사배정에 대한 소스코드

<소스코드>

#include <cstdio>
using namespace std;

int e[500][500];
bool visit[500];
int parent[500];
int N, M;

int DFS(int start) {
	if (start == N + 1+ M) return true;
	visit[start] = true;
	for (int i = 0; i <= N + 1+M; i++) {
		if (!visit[i] && e[start][i] > 0) {
			parent[i] = start;
			if (DFS(i)) return true;
		}
	}
	return false;
}

void tracking(int start) {
	if (start == 0) return;
	int p = parent[start];
	e[p][start]--;
	e[start][p]++;
	tracking(p);
}

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; i++) {
		e[0][i] = 1;
		int a;
		scanf("%d", &a);
		for (int j = 0; j < a; j++) {
			int b;
			scanf("%d", &b);
			e[i][N+b] = 1;
		}
	}
	for (int i = N+1; i <= N+ M; i++) e[i][N+M+1] = 1;
	
	int cnt = 0;
	while (DFS(0)) {
		cnt++;
		tracking(N+M+1);
		for (int i = 0; i <= N + 1+M; i++)visit[i] = false;
	}
	printf("%d\n", cnt);
	return 0;
}