Edmonds-Karp Best Practice

수정필요

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
/*
유량 그래프 기본 설명::
유량 그래프란 : 간선에 가중치 대신 유량 개념을 적용한 알고리즘으로써 
간선에 용량(capacity)과 유량(flow) 개념이 있다.
1. 유량은 최대 용량을 초과할 수 없으며, 각 정점은 자신이 받은 유량만큼만 유량을 흘려보낼 수 있다.
2. 모든 유량의 최초 발생은 시작 정점(S)에서만 발생시킬 수 있으며, 모든 유량은 최종적으로 도착 정점(T)로만 흘러들어간다. (용량에 막혀 흐르지 못하는 유량 제외)
3. 유량이 흐르면 간선의 반대방향으로 그 유량만큼의 음의 유량이 흐르는 것으로 취급한다. 
 
포드 풀커슨 알고리즘 / 에드몬드 카프 알고리즘
포드 풀커슨 알고리즘은 실제 문제 풀이에서 사용하기엔 worst case 해결이 불가능하므로 에카 알고리즘 사용
 
1. 증가 경로 탐색
단순 경로이며 모든 간선에 용량이 남은 경로를 증가 간선이라고 함
2. 경로 중, 차단 간선 탐색
경로상 용량 - 유량의 값이 최소인 간선을 차단 간선이라고 함
3. 경로의 모든 간선에 차단 간선의 용량만큼 유량 추가
3번 성질을 만족시키기 위해 f(u, v) += flow를 했으면 f(v, u) -= flow도 실행해야함
 
위 1, 2, 3 번 과정을 더 이상의 증가경로가 없을 때 까지 반복함.
 
이 후 도착 정점 T에 모인 유량을 합산
*/
 
//예제 6086 최대 유량 해결
//A 1 -> Z 26
//간선과 용량 / 유량은 별도의 배열로 관리하는것이 편리함.
 
inline int CtoN(char c) {
	if (c >= 97) return c - 70;
	return c - 64;
}
 
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int m; cin >> m;
	vector<vector<int>> arr(53);
	
	vector<vector<int>> flow(53, vector<int>(53));
	vector<vector<int>> capacity(53, vector<int>(53));
 
	for (int i = 1; i <= m; i++) {
		char s, d; int v;
		cin >> s >> d >> v;
		int sn = CtoN(s);
		int dn = CtoN(d);
		arr[sn].push_back(dn);
		arr[dn].push_back(sn);//역방향간선
		capacity[sn][dn] += v;
		capacity[dn][sn] += v;
	}
 
	int tf = 0;
 
	while (true) {
		vector<int> pathlist;
		vector<int> prevv(53, -1);
		queue<int> q;
		const int source = CtoN('A'); const int tank = CtoN('Z');
		q.push(source);
		
		// source -> tank 인 증가 경로 탐색 
		while (!q.empty() && prevv[tank] == -1) {
			auto current = q.front(); q.pop();
			for (auto nx : arr[current]) {
				int c = capacity[current][nx];
				int f = flow[current][nx];
				if (c > f && prevv[nx] == -1) {
					q.push(nx);
					prevv[nx] = current;
				}
			}
		}
 
		if (prevv[tank] == -1) break;
 
		int mnf = 2147483647;
		int cv = tank;
		while (cv != source) {
			int c = capacity[prevv[cv]][cv];
			int f = flow[prevv[cv]][cv];			
			mnf = min(mnf, c - f);
			cv = prevv[cv];
		}
 
		cv = tank;
		while (cv != source) {
			flow[prevv[cv]][cv] += mnf;
			flow[cv][prevv[cv]] -= mnf;
			cv = prevv[cv];
		}
 
		tf += mnf;
	}
 
	cout << tf << "\n";
 
	return 0;
}