백준 6086번 최대 유량

문제 링크 : https://www.acmicpc.net/problem/6086

문제풀이

사용한 알고리즘 : Network Flow

강산님의 블로그 글을 참고하여 작성하였습니다.

(0) 생각

 네트워크 유량을 쓸 줄 아는가 묻는 문제였습니다.

 에드몬드 카프 알고리즘을 사용하여 풀이하였습니다.

(1) 코드 16~18

 각 노드간 간선을 저장할 vector 배열을 만들어 주었습니다.

 'c[i][j] : i->j 간선의 용량' ,

 'f[i][j] : i->j 간선의 유량' 이라고 설정해 주었습니다.

(2) 코드 43~78

 에드몬드 카프 알고리즘을 구현해줍니다.

 시작점(S)에서 도착점(T)까지 경로가 있는지 BFS로 탐색 해줍니다.

 경로가 존재 한다면, 해당 경로 상의 가장 작은 '용량-유량' 값을 구해주어, 이 값을 경로 상의 모든 간선에 더해줍니다.

 이때 구하고자 하는 답에도 해당 값을 더해줍니다.

 S ~ T 사이의 경로가 없을 때까지 반복해줍니다.

	#include <iostream>
	#include <queue>
	#include <vector>
	using namespace std;
	const int MAX_V = 52; // 알파벳 대,소문자 총 52 개
	const int INF = 1000000000;
	// 알파벳 -> 숫자 변환
	int CtoI(char c) {
	// index: 대문자 = 0~25 , 소문자 = 26~51
	if (c <= 'Z') return c - 'A'; // 대문자가 소문자보다 아스키 코드 작다.
	return c - 'a' + 26;
	}
	int N; // 간선개수
	vector<int> adj[MAX_V]; // 간선
	int c[MAX_V][MAX_V]; // c[i][j] : i -> j 가는 용량
	int f[MAX_V][MAX_V]; // f[i][j] : i -> j 가는 유량
	int Prev[MAX_V]; // 지나온 경로 기억하기 위해
	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; ++i) {
	char a, b;
	int u, v, w;
	cin >> a >> b >> w;
	u = CtoI(a);
	v = CtoI(b);
	c[u][v] += w;
	c[v][u] += w; // 역방향 간선에도 용량 추가
	adj[u].push_back(v);
	adj[v].push_back(u);
	}
	int total = 0; // 총 유량 (구하고자 하는 답 )
	int S = CtoI('A'); // 소스 ( 물 나오는 데 )
	int T = CtoI('Z'); // 싱크 ( 물 들어가는 데)
	while (1) { // 증가 경로 못찾을 때까지 반복
	// BFS 로 증가경로 찾는다.
	fill(Prev, Prev + MAX_V, -1);
	queue<int> Q;
	Q.push(S); // 시작점
	while (!Q.empty() && Prev[T] == -1) {
	int curr = Q.front();
	Q.pop();
	for (int next : adj[curr]) {
	// c[i][j] - f[i][j] > 0 : i->j 가능한 용량 여유가 남았는가?
	// prev[next] = -1 : 아직 방문되지 않은 점인가?
	if (c[curr][next] - f[curr][next] > 0 && Prev[next] == 0) {
	Q.push(next);
	Prev[next] = curr; // 경로 기억
	if (next == T) break; // T 도착
	}
	}
	}
	// T 로 가는 경로가 더 없으면 루프 탈출
	if (Prev[T] == -1) break;
	// 차단간선 ( 경로상 가장 허용치가 낮은 간선 ) 찾기
	int Flow = INF;
	for (int i = T; i != S; i = Prev[i]) // Prev[i] -> i 였음을 기억
	Flow = min(Flow, c[Prev[i]][i] - f[Prev[i]][i]);
	// 찾은 flow 만큼 해당 경로에 유량을 흘려줌
	for (int i = T; i != S; i = Prev[i]) {
	f[Prev[i]][i] += Flow;
	f[i][Prev[i]] -= Flow; // 역방향 간선은 가능한 용량 증가!! (즉 유량 감소)
	}
	// 총 유량 값 증가
	total += Flow;
	}
	cout << total << '\n';
	return 0;
	}

view raw BOJ 6086.cpp hosted with ❤ by GitHub