[백준 6086] 최대 유량

문제 링크 => 6086번: 최대 유량 (acmicpc.net)

6086번: 최대 유량

---

최대 유량 문제이다.

 

Edmond-carp Algorithm 을 이용하여 해결하였다.

 

문제에서 활용될 노드는 'A' ~ 'Z', 'a' ~ 'z' 이므로 총 52개의 노드가 필요하다.

 

Input 을 보면 from, to, capacity 가 제공되는데 여기서 from, to 가 중복해서 나타나는 경우가 존재한다.

 

따라서 capacity를 노드에서 노드로 이동하는 2차원 배열 c[x][y] 에 대하여 c[from][to] += capacity, c[to][from] += capacity 를 해줘야 한다. (양방향으로 흐르므로 from => to, to=> from 동시에 capacity를 체크해줘야 함)

 

최대유량을 구하기 위한 모든 세팅이 완료되면 start : 'A', end : 'Z' 임을 이용하여 Edmond-carp Algorithm 을 이용하여 구해주면 끝이다.

 

풀이 code

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <vector>
#include <stack>
#include <queue>
#include <stdio.h>
#include <iomanip>
#include <map>
#include <cstdlib>

#define INF 100000000

using namespace std;

int N, result;
int c[60][60], f[60][60], d[60];
vector<int> v[60];

void solve(int start, int end) {
	while (1) {
		fill(d, d + 60, -1);
		queue<int> q;
		q.push(start);

		// Execute BFS 
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			for (int y : v[x]) {
				if (c[x][y] - f[x][y] > 0 && d[y] == -1) {
					q.push(y);
					d[y] = x; //경로를 기억시킴
				}
			}
		}

		// 모든 경로를 다 찾은 경우 탈출
		if (d[end] == -1) break;

		int flow = INF;
		for (int i = end; i != start; i = d[i]) {
			flow = min(flow, c[d[i]][i] - f[d[i]][i]);
		}
		for (int i = end; i != start; i = d[i]) {
			f[d[i]][i] += flow;
			f[i][d[i]] -= flow;
		}
		result += flow;
	}

	cout << result << endl;
}

void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		char c1, c2;
		int capacity;
		cin >> c1 >> c2 >> capacity;
		int from = c1 - 'A', to = c2 - 'A';

		v[from].push_back(to);
		v[to].push_back(from);
		c[from][to] += capacity;
		c[to][from] += capacity;
	}
}

int main(void) {

	input();
	solve(0, 25);

	return 0;
}