[BOJ] #6086 _ 최대 유량

[최대 유량] https://www.acmicpc.net/problem/6086

6086번: 최대 유량

네트워크 플로우 문제이다.

해당 문제는 양방항 그래프라는 점을 유의해서 풀어야 한다.

 

[ Ford-Fulkerson Algorithm ]

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>

#define MAX 52
#define INF 999999999

using namespace std;

int c[MAX][MAX], f[MAX][MAX], visit[MAX];
vector<int> adj[MAX];

int charToint(char chr);
int maxFlow(int S, int T);
int dfs(int a, int T, int flow);
int main() {
	int N, capacity;
	char p1, p2, tmp;
	scanf("%d%c", &N, &tmp);
	for (int i = 0; i < N; i++) {
		int a, b;
		scanf("%c %c %d%c", &p1, &p2, &capacity, &tmp);
	
		a = charToint(p1);
		b = charToint(p2);

		adj[a].push_back(b);
		adj[b].push_back(a);
		c[a][b] += capacity;
		c[b][a] += capacity;
	}

	printf("%d\n", maxFlow(charToint('A'), charToint('Z')));

	return 0;
}

int charToint(char chr) {
	if (chr < 'a') return chr - 'A';
	else return (chr - 'a') + 26;
}

int maxFlow(int S, int T) {
	int result = 0;

	while (1) {
		memset(visit, 0, sizeof(visit));
		int flow = dfs(S, T, INF);
		if (!flow) break;
		result += flow;
	}

	return result;
}

int dfs(int a, int T, int flow) {
	if (visit[a]) return 0;
	visit[a] = 1;

	if (a == T) return flow;

	for (int i = 0; i < adj[a].size(); i++) {
		int b = adj[a][i], now_flow = c[a][b] - f[a][b];
		if (now_flow <= 0) continue;

		int result = dfs(b, T, min(flow, now_flow));
		if (result) {
			f[a][b] += result;
			f[b][a] -= result;
			return result;
		}
	}

	return 0;
}

 

[ Edmonds-Karp Algorithm ]

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>

#define MAX 52
#define INF 999999999

using namespace std;

int c[MAX][MAX], f[MAX][MAX], visit[MAX];
vector<int> adj[MAX];

int charToint(char chr);
int maxFlow(int S, int T);
int bfs(int S, int T);
int main() {
	int N, capacity;
	char p1, p2, tmp;
	scanf("%d%c", &N, &tmp);
	for (int i = 0; i < N; i++) {
		int a, b;
		scanf("%c %c %d%c", &p1, &p2, &capacity, &tmp);

		a = charToint(p1);
		b = charToint(p2);

		adj[a].push_back(b);
		adj[b].push_back(a);
		c[a][b] += capacity;
		c[b][a] += capacity;
	}

	printf("%d\n", maxFlow(charToint('A'), charToint('Z')));

	return 0;
}

int charToint(char chr) {
	if (chr < 'a') return chr - 'A';
	else return (chr - 'a') + 26;
}

int maxFlow(int S, int T) {
	int result = 0;

	while (1) {
		int flow = bfs(S, T);
		if (!flow) break;
		result += flow;
	}

	return result;
}

int bfs(int S, int T) {
	memset(visit, -1, sizeof(visit));

	queue<int> q;
	q.push(S);
	while (!q.empty()) {
		int a = q.front();
		q.pop();
		for (int i = 0; i < adj[a].size(); i++) {
			int b = adj[a][i];
			if (c[a][b] - f[a][b] <= 0) continue;
			if (visit[b] != -1) continue;

			q.push(b);
			visit[b] = a;
			if (b == T) break;
		}
	}

	if (visit[T] == -1) return 0;

	int flow = INF;
	for (int i = T; i != S; i = visit[i]) {
		flow = min(flow, c[visit[i]][i] - f[visit[i]][i]);
	}

	for (int i = T; i != S; i = visit[i]) {
		f[visit[i]][i] += flow;
		f[i][visit[i]] -= flow;
	}

	return flow;
}