17412 도시 왕복하기 1 [ 깔끔한 알고리즘 문제풀이 ]

c++17

 

 

문제 한번에 맞아서 기분좋은나머지 글써봅니다.

 

 

문제 풀러가기

17412번: 도시 왕복하기 1

 

 

문제

 

난이도

플래티넘 IV

 

 

문제 유형

네트워크 유량

 

 

해법

 이 문제는 난이도에 비해서 문제유형이 뭔지만 알면, 쉽게 풀리는문제입니다.

문제에서 범위가 1번도시부터 N번도시까지라고했지만,

어쨌든 우리가 최종적으로 원하는 최대유량및 결과값은 1번도시부터 2번도시로 가는 최대유량을 구해야합니다.

따라서 시작점을 1로하고 끝점을 2로 설정한다음 네트워크유량 알고리즘 돌려주면 됩니다.

 

 그리고 정점들간의 드는 비용은 모두 1로 통일해주어야합니다.

왜냐하면 문제에 보면 예제입력칸에 드는 비용을 따로 입력을 안해주었기때문입니다.

단지 "왔다갔다"만 하게만 하면됩니다.

이 문제같은 경우는 네트워크유량 알고리즘에 관한 사전지식이 없으면 풀기힘들겁니다.

 

 

소스코드

#include <bits/stdc++.h>

#define MAX (401)
constexpr int INF = std::numeric_limits<int>::max(); //무한대수값 정의.

int c[MAX][MAX], f[MAX][MAX]; //c는 용량, f는 유량입니다.
std::vector<int>a[MAX]; //그래프의 정점들을 저장한 배열

int networkFlow(int N, int start, int end){ //보편적인 네트워크 유량 알고리즘함수
	int ans = 0; //start에서 end정점까지 가는데 드는 최대유량.
	
	while(true){ //여기서부터가 네트워크유량알고리즘 시작부분입니다.
		std::vector<int>visit(N + 1, -1);
		std::queue<int>q;
		q.push(start);
		while(!q.empty()){
			int x = q.front();
			q.pop();
			
			for(int i=0;i<a[x].size();++i){
				int y = a[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;
		}
		
		ans += flow;
	}
	return ans;
}

int main() {
	int N, P;
	std::cin >> N >> P; //문제에서의 N과 P
	for(int i=0;i<P;++i){
		int al, b;
		std::cin >> al >> b;
		
		a[al].push_back(b); //서로를 가리킵니다.
		a[b].push_back(al); //서로를 가리킵니다.
		c[al][b] = 1; //비용은 모두 1이여야한다. (설명은 글에 적어놓았습니다.)
	}
	
	std::cout << networkFlow(N, 1, 2); //최대정점N과 1부터 2까지의 드는 최대유량 반환.
}

 

 

 

궁금한 부분있으면 댓글로 질문주세요!