네트워크 플로우(Maximum flow)

// 네트워크 플로우

// 네트워크 상에서 최대한 얼마나 많은 양의 유량을 흘려보낼수 있는가를 묻는 알고리즘
// 일반적으로 BFS를 이용한 에드몬드 카프 알고리즘을 이용한다
// 에드몬드 카프 알고리즘은 음의 유량을 반드시 고려해주어야 한다
// 플로우의 경우 순서는 상관없다
// 최대유량은 시작점에서 나가는 유량 == 도착점에서 들어오는 유량

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;

#define MAX 10001
#define inf 987654321

int N;
ll cp[MAX][MAX], flow[MAX][MAX], pre[MAX]; // cp : capacity, flow : flow, pre : previous visit now
vector<int> v[MAX]; // 서로 연결된 정점

ll maxflow(int start, int end) {
	queue<int> q;
	ll ret = 0; // ret is maximum flow(answer)

	while (1) { // end 정점에 방문하지 못했다면 계속적으로 반복한다

		while (!q.empty()) q.pop();
		memset(pre, -1, sizeof(pre)); // 방문배열을 초기화!
		q.push(start);

		while (!q.empty()) {
			int num = q.front();
			q.pop();
			if (num == end) break; // 만약 끝정점에 도달했다면 탐색끝

			for (int i = 0; i < v[num].size(); i++) {
				// 흐를 수 있는 유량이 있고, 이 노드를 방문하지 않았다면
				if (cp[num][v[num][i]] - flow[num][v[num][i]] > 0 && pre[v[num][i]] == -1) {

					q.push(v[num][i]), pre[v[num][i]] = num;
				}
			}
		}
		if (pre[end] == -1) break;

		ll min_flow = inf; // 가장 많이 흐를 수 있는 유량을 확인하기 위해 INF로 초기화해서 min으로 값을 맞춰간다
		for (int i = end; i != start; i = pre[i]) {
			min_flow = min(min_flow, cp[pre[i]][i] - flow[pre[i]][i]);
		}
		for (int i = end; i != start; i = pre[i]) {
			flow[pre[i]][i] += min_flow; // 현재 노드에서 다음 노드로 흐르는 유량은 + 처리를 해준다
			flow[i][pre[i]] -= min_flow; // 다음 노드에서 현재 노드로 흐르는 유량은 - 처리를 해준다
		}
		ret += min_flow;// ret는 최대유량으로, min_flow를 계속 더해주면 된다
	}

	return ret;
}

int main() {

	while (1) {
		// a <-> b 를 서로 연결해준다
		v[a].push_back(b);
		v[b].push_back(a);
		// 용량은 양쪽으로 흐르기 때문에 a<->b 방향 모두 += w 처리를 해준다
		cp[a][b] += w;
		cp[b][a] += w;
	}
	
    maxflow(start, end);
}