[백준/C++] 6086번 - 최대 유량

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

이 문제는 network Flow문제와 같다. 

같은 지점에서 같은 지점으로 연결된 관은 병렬연결이므로 흐를 수 있는 유량에 더해준다.

그리고 양방향으로 흐를 수 있다고 했으므로 이 점도 고려해 흐를 수 있는 유량에 더해주면, Network Flow 문제가 된다. 

​

Network Flow 문제를 푸는 방법을 간단하게 소개하면

 

1. 유량 보존의 법칙

•  유체가 나오는 부분을 source, 들어오는 부분을 sink라고 하는데, 이 두 부분을 제외하고는 각 정점에서 들어오는 유량과 나가는 유량이 일치해야 한다.

2. 유량의 대칭성

• f(u, v) = A 가 u에서 v로 A 만큼 유체가 흐르는 것을 의미한다고 하자. 그러면 f(u, v) = -f(v, u) 가 성립한다. 왜냐하면 u에서 A양만큼 v로 유체가 흐른다면, v에서 u로 A양만큼 빠져나갔으므로 -A만큼 들어오는 것이기 때문이다.

3. 용량 제한 속성

• 두 간선에서 흐르는 유량은 간선의 최대 용량을 넘을 수 없다.

여기서 유량의 대칭성을 이용하면 막힌 길 처럼 보여도 유체를 더 보낼 수 있는 다른 경로가 있는지 찾을 수 있다. 이를 이용해 최대 유량을 구할 수 있다.

 

위 점을 유의하면서 BFS나 DFS로 경로를 탐색해, 최대 유량을 구할 수 있다.

 

 

[아이디어 정리]

1. 유체가 흐를 수 있는 용량을 2차원 벡터에 기록한다.
2. BFS를 이용해 유체의 경로를 찾고, 경로를 찾았다면 역으로 경로를 따라 흐를 수 있는 유체의 최대 양을 찾는다.
3. 더 이상 유체가 흐르지 못한다면, sink에서(A에서) 나오는 유량이 얼마나 되는지 계산해 return한다.

 

 

Code

 

 

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <sstream>
using namespace std;

int main() 
{
	int N, value, a,b;
	char st, ed;
	vector<vector<int>> flow(52, vector<int>(52, 0));
	vector<vector<int>> cur(52, vector<int>(52,0));
	vector<vector<int>> pline(52);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> st >> ed >> value;
		//cin >> a >> b >> c;
		if (st <= 'Z')
			a= st - 'A';
		else
			a = st-'a' + 26;
		if (ed <= 'Z')
			b = ed-'A';
		else
			b = ed- 'a' + 26;
		flow[a][b] += value;
		flow[b][a] += value;
		pline[a].push_back(b);
		pline[b].push_back(a);
	}

	int now, v;
	while (true) 
	{
		queue<int> Q;
		Q.push(0);
		vector<int> dirV(52, -1); //이전 지점을 저장할 vector
		v = 1000;
		while (!Q.empty()) 
		{
			now = Q.front();
			Q.pop();
			if (now == 25) 
			{
				break;
			}

			for (int i = 0; i < pline[now].size(); i++) 
			{
				if (dirV[pline[now][i]] == -1&&(cur[now][pline[now][i]]<flow[now][pline[now][i]]))  //방문하지 않았고 유량이 흐를 수 있다면
				{
					dirV[pline[now][i]] = now;
					Q.push(pline[now][i]);
				}
			}
		}
		if (dirV[25] == -1)
		{
			// 모든 경로 탐색 완료
			break;
		}
			// 경로 유량 측정
		for (int i = 25; i != 0; i = dirV[i]) //i는 도착지점 dirV[i]가 
		{
			v = min(v, flow[dirV[i]][i] - cur[dirV[i]][i]);
		}

		for (int i = 25; i != 0; i = dirV[i])
		{
			cur[dirV[i]][i] += v;
			cur[i][dirV[i]] -= v;
		}
	}

	int ans = 0;
	for (int i=0; i<52; i++)
	{
		ans+=cur[0][i];
	}
	cout << ans;
	return 0;
}

 

---

 

 

오랜만에 알고리즘 공부를 하느라 시간을 썼다...

문제를 풀 때 파이프에서 흐르는 유체가 단방향인 줄 알고 풀 뻔;;

 

6086번: 최대 유량

[참고]

https://www.crocus.co.kr/741

https://m.blog.naver.com/intelliz/222836637887