[C++] 백준 6086번 최대 유량

네트워크 플로우 문제입니다.

A부터 Z까지 최대 유량을 구해야합니다.
주의해야할 점은 유량이 양방향으로 흐를 수 있으므로,
A B 3이라고 입력 받았을 때
A->B 3
B->A 3
두 방향 전부 용량을 추가해야합니다.

A에서 Z까지 BFS로 흐를 수 있는 길을 찾고
그 길에서 최소 유량을 구합니다.
최소 유량의 값을 result에 더해줍니다.

음의 유량도 고려해야하며,
어떤 배수관에서 왔는지 체크도 해주어야합니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#define MAX 52
#define INF 987654321

using namespace std;

int N;
int result = 0;
int p[MAX];
int c[MAX][MAX];
int f[MAX][MAX];
vector<int> v[MAX];

char ctoi(char x)
{
	if (x <= 'Z') {
		return x - 'A';
	}
	return x - 'a' + 26;
}

int main(int argc, char* argv[])
{
	memset(c, 0, sizeof(c));
	memset(f, 0, sizeof(f));

	scanf("%d", &N);
	getchar();

	for (int i = 0; i < N; ++i) {
		char a, b;
		int num;

		scanf("%c %c %d", &a, &b, &num);
		getchar();

		a = ctoi(a);
		b = ctoi(b);

		c[a][b] += num;
		c[b][a] += num;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	int start = ctoi('A');
	int end = ctoi('Z');

	while (1) {
		memset(p, -1, sizeof(p));
		queue<int> q;
		q.push(start);

		while (!q.empty()) {
			int cur = q.front();
			q.pop();

			if (cur == end) {
				break;
			}

			for (int i = 0; i < v[cur].size(); ++i) {
				int next = v[cur][i];

				if (p[next] == -1 && c[cur][next] - f[cur][next] > 0) {
					q.push(next);
					p[next] = cur;
				}
			}
		}

		if (p[end] == -1) {
			break;
		}

		int minFlow = INF;
		for (int i = end; i != start; i = p[i]) {
			minFlow = min(minFlow, c[p[i]][i] - f[p[i]][i]);
		}

		for (int i = end; i != start; i = p[i]) {
			f[p[i]][i] += minFlow;
			f[i][p[i]] -= minFlow;
		}

		result += minFlow;
	}

	printf("%d\n", result);

	return 0;
}