[BOJ] 6086 : 최대 유량

Drakk·2021년 7월 9일

C boj 네트워크 유량 알고리즘

알고리즘 문제풀이

목록 보기

1/22

💉문제 내용

문제 풀러가기

💉입출력

🧺입력
첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위치에 파이프의 용량이 주어진다.

🧺출력
첫째 줄에 A에서 Z까지의 최대 유량을 출력한다.

🔋예제 입출력

🔮예제 입력
5
A B 3
B C 3
C D 5
D Z 4
B Z 6

🔮예제 출력
3

💉문제 분석

🔋분류

네트워크 유량
최대 유량

🔋난이도

플래티넘 IV

💉문제 풀이

🔋해법

해법은 매우 간단합니다.
일반적인 네트워크 유량알고리즘에서 살짝 변형시키면됩니다.
이 문제의 핵심은 문제 맨마지막에 나와있는 "파이프는 역방향으로 흐를 수 있다."입니다.
이 점만 유의하시면, 쉽게 푸실 수 있으실겁니다.

🔋소스코드

#include <bits/stdc++.h>

#define MAX (701)
#define ctoi(x) (x - 'A')

constexpr int INF = std::numeric_limits<int>::max();

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

//N : 검사할 정점의 갯수, start : 시작점, end : 끝점
int networkFlow(int N, int start, int end){
	int result = 0; //최대유량을 저장할 변수
	
	while(true){ //일반적인 네트워크 유량알고리즘 실행부분입니다.
		std::vector<int> visit(N, -1);
		std::queue<int> q;
		q.push(start);
		while(!q.empty()){
			int x = q.front();
			q.pop();
			
			for(int i=0;i<adj[x].size();++i){
				int y = adj[x][i];
				if(c[x][y] - f[x][y] > 0 && visit[y] == -1){
					visit[y] = x;
					q.push(y);
					if(y == end) break;
				}
			}
		}
		
		if(visit[end] == -1) break;
		
		int flow = INF;
		for(int i = end;i!=start;i=visit[i]) flow = std::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;
		}
		
		result += flow;
	}
	return result;
}

int main() {
	int N;
	std::cin >> N;
	for(int i=0;i<N;++i){
		char a, b; //a와 b는 반드시 char로 하셔야합니다.
		int d;
		std::cin >> a >> b >> d;
		int newa = ctoi(a);
		int newb = ctoi(b);
		adj[newa].push_back(newb); //서로를 가리킵니다.
		adj[newb].push_back(newa); //서로를 가리킵니다.
        
        	//이부분때문에 좀 헤맸습니다.
            	//이부분또한 문제 맨마지막줄에나와있는부분에 의해서 서로를 가리킵니다.
                //왜냐하면 파이프는 역방향으로도 흐를 수 있기때문이다.
		c[newa][newb] += d;
		c[newb][newa] += d;
	}
	
	std::cout << networkFlow(MAX, ctoi('A'), ctoi('Z'));
}