[백준BOJ] 6086 최대 유량

https://www.acmicpc.net/problem/6086

6086번: 최대 유량

 

---

문제해설

"에드몬드 카프 알고리즘(Edmonds-Karp algorithm)" 을 활용한 "네트워크 플로우" 문제입니다.

문제 제목부터가 "최대 유량"이기 때문에, 유량관련 알고리즘을 사용해야 합니다.

에드몬드 카프 알고리즘을 모르시는분은 밑의 동영상을 참고하시면 좋을 것 같습니다.

 

https://youtu.be/Wn51_ypG_T8

위, 유튜브에서 올라온 코드 그대로 작성하면 AC를 맞을 수 있습니다.

단, 조심해야 할 것은

입력 부분에서 

		map[A].push_back(B);
		map[B].push_back(A);
		c[A][B] += w;
		c[B][A] += w;

위와 같이, 양방향에 대해서 처리를 해줘야 됩니다.

주석을 통해서 자세한 풀이를 확인해주세요.

---

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
//--------------------------------------------------------------------------------------
#define MAX_N 52

int c[MAX_N][MAX_N]; // 흐르는 양
int f[MAX_N][MAX_N]; // 흐르고 있는 양
int visit[MAX_N]; // 한번 que가 돌때마다 visit 이 -1로 초기화 된다.
vector<int> map[MAX_N];

// 애드몬드 카프 알고리즘
int maxFlow(int start, int end) {
	int ret = 0;
	while (1) {
		memset(visit, -1, sizeof(visit)); // 모든 정점 방문 초기화
		queue<int> q;
		q.push(start); // start 점에서 end 점까지 흘려 보낸다.
		while (!q.empty()) { 
			int front = q.front(); q.pop();
			for (int i = 0; i < map[front].size(); i++) {
				int e = map[front][i];
				if (c[front][e] - f[front][e] > 0 && visit[e] == -1) {
					// 흐를 수 있다 && 이번 BFS에서 흐른적이 없다.
					q.push(e); 
					visit[e] = front; // front에서 e로 흘렀다는 것을 알려준다.
					if (e == end) break; // end 점을 찾게되면 flow 중지
				}
			}
		}
		// 모든 경로를 찾은 경우
		if (visit[end] == -1) break; // BFS에서 end 점을 방문하지 않았다 -> 더이상 흐르는 경우가 없다.
		int flow = INT_MAX; // 최솟값을 찾기 위함
		for (int i = end; i != start; i = visit[i]) {
			flow = min(flow, c[visit[i]][i] - f[visit[i]][i]);
		}

		for (int i = end; i != start; i = visit[i]) {
			// 음의 간선이 있다고 생각함으로써 모든 경우의 수를 탐색 할 수 있게 된다.
			f[visit[i]][i] += flow;
			f[i][visit[i]] -= flow;
		}
		ret += flow;
	}
	return ret;
}

int getID(char c) {
	int ret;
	if (c >= 97) {
		ret = c - 97;
		ret += 26;
	}
	else {
		ret = c - 65;
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		char a, b; int w; cin >> a >> b >> w;
		int A = getID(a);
		int B = getID(b);
		//cout << a << " : " << A << " " << b << " : "<< B << endl;
		map[A].push_back(B);
		map[B].push_back(A);
		c[A][B] += w;
		c[B][A] += w;
	}
	cout << maxFlow(0, 25) << "\n";
}

---

기타