[BOJ] 2316 : 도시 왕복하기 2

Drakk·2021년 7월 14일

2316 C boj 그래프 네트워크유량 백준 알고리즘 최대유량

알고리즘 문제풀이

목록 보기

5/22

💉문제 내용

문제 풀러가기

💉입출력

🧺입력
첫째 줄에 두 정수 N(3 ≤ N ≤ 400), P(1 ≤ P ≤ 10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 서로 다른 두 도시의 번호가 주어진다.

🧺출력
첫째 줄에 왔다 갔다 할 수 있는 최대 횟수를 출력한다.

🔋예제 입출력

🔮예제 입력1
5 5
1 3
3 2
1 5
5 4
4 2

🔮예제 출력1
2

🔮예제 입력2
6 7
1 3
3 2
1 4
4 2
1 5
5 6
6 2

🔮예제 출력2
3

🔮예제 입력3
7 8
1 3
1 4
3 5
4 5
5 6
5 7
6 2
7 2

🔮예제 출력3
1

💉문제 분석

🔋분류

최대 유량, 네트워크 유량, 분할 정복

🔋난이도

플래티넘III

💉문제 풀이

🔋해법

우선은 이 문제는 네트워크유량과 분할정복을 사용하여 풀수있습니다.
네트워크유량 알고리즘함수쪽은 전혀건드리지않았구요, 이 문제에서는 분할 정복이라는것이 사용됩니다.

한 정점내에 다른정점으로부터 연결되오는 in과 다른정점으로 연결하는 out으로 정점을 분할하여 풀수있습니다.

우선은 in은 1~401까지 out은 402~801까지로 설정했습니다.
우선 1부터 N만큼의 정점이 존재합니다.
따라서, 정점의 갯수인 1부터 N의 정점들을 모두 in, out정점으로 분할하여 서로를 가리키도록하며, 이때 용량은 1이됩니다.

그리고 언제나 out정점이 in정점을 가리켜야하므로,
{a의 out} -> {b의 in}, {b의 in} -> {a의 out}
{b의 out} -> {a의 in}, {a의 in} -> {b의 out}
이런식으로 가리켜야하며, 이때 용량은 양방향으로 모두 1로 설정합니다.

마지막으로 시작지점은 1이아닌 OUT + 1이됩니다.
마찬가지로 현재 정점의 out이 다른정점의 in을 가리켜야하기때문이죠.

🔋소스코드

#include <iostream> //2316
#include <queue>
#include <vector>

#define MAX (802)

constexpr int OUT = 401;
constexpr int INF = 987654321;

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

int networkFlow(int start, int end){
	int ans = 0;
	
	while(true){
		std::vector<int> visit(MAX, -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(visit[y] == -1 && c[x][y] - f[x][y] > 0){
					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;
		}
		
		ans += flow;
	}
	
	return ans;
}

int main(){
	std::cin.tie(0);
	std::cout.tie(0);
	std::ios_base::sync_with_stdio(0);
	
	int N, P;
	std::cin >> N >> P;
	
	for(int i=1;i<=N;++i){
		adj[i].push_back(OUT + i);
		adj[OUT + i].push_back(i);
		c[i][OUT + i] = 1;
	}
	
	for(int i=0;i<P;++i){
		int a, b;
		std::cin >> a >> b;
		
		adj[OUT + a].push_back(b);
		adj[b].push_back(OUT + a);
		c[OUT + a][b] = 1;
		
		adj[OUT + b].push_back(a);
		adj[a].push_back(OUT + b);
		c[OUT + b][a] = 1;
	}
	
	std::cout << networkFlow(OUT + 1, 2);
}