백준, boj) 2316. 도시 왕복하기2 ( C / C++ )

1. 문제 링크

https://www.acmicpc.net/problem/2316

2316번: 도시 왕복하기 2

 

2. 문제 개요

N개의 도시가 P개의 양방향 길로 연결되어 있다.

1 --- 2 번 도시를 오갈 때, 반드시 1개 이상의 도시를 중간에 거쳐야 한다. 한번 방문한 도시는 두 번 이상 방문하지 않으려 한다. 입력에는 1번 도시와 2번 도시를 연결하는 길은 없다.

왔다 갔다 할 수 있는 최대 횟수를 구하기.

 

3. 문제 힌트

 Network flow문제이다.

한 도시를 두 번 이상 방문하지 않으려고 할 때 어떻게 하면 구분할 수 있을까?

 

-정점 분할

  하나의 마을을 2개의 정점으로 분할시켜보자.

정점분할

 

4. 문제 풀이

네트워크 플로우 문제는 디자인하는 능력이 절반이상인것 같다.

한 마을을 2번 이상 거치지 않도록 하기위해 마을을 2개의 정점으로 분리하고 용량 1의 간선으로 연결한다.

 

그리고 마을 사이에는 out -> in으로 가는 간선과 out -> in으로 가는 간선을 다 연결해주고, 용량 1로 설정해준다.

 

포드 풀커슨 알고리즘을 사용하여 src에서 dest까지 실행한다.

 

5. 코드

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int out = 400;
const int src = 401, dest = 2;


//house, [in,out]
vector<int>v[801]; //index로부터 출발하는 간선
int c[801][801], f[801][801];
int n, m, ans;


void edmondkarp()
{
	while (1)
	{
		int p[801];
		fill(p, p + 801, -1);

		queue<int>q;
		q.push(src);
		p[src] = src;

		while (!q.empty())
		{
			int cur = q.front(); q.pop();

			int len = v[cur].size();
			for (int i = 0; i < len; ++i)
			{
				int next = v[cur][i];

				//유량이 남아있고 방문하지 않았다면,
				if (c[cur][next] - f[cur][next] > 0 && p[next] == -1)
				{
					p[next] = cur;
					q.push(next);
					if (next == dest)
						break;
				}
			}
		}
		if (p[dest] == -1) 
			break;

		int minflow = 987654321;
		for (int i = dest; i != src; i = p[i])
			minflow = min(minflow, c[p[i]][i] - f[p[i]][i]);

		//minflow만큼 흐르게 될것.
		for (int i = dest; i != src; i = p[i])
		{
			f[p[i]][i] += minflow;
			f[i][p[i]] -= minflow;
			
		}
		ans += minflow;
	}
	return;
}
int main()
{
	scanf("%d %d", &n, &m);
	//in 1~400, out 401 ~800....

	//internal
	for (int i = 1; i <= n; ++i)
	{
		v[i].push_back(i + out);
		v[i + out].push_back(i);
		
		//i -> i+out..
		c[i][i + out] = 1;
	}

	//external
	for (int i = 0; i < m; ++i)
	{
		int from, to;
		scanf("%d %d", &from, &to);

		v[out + from].push_back(to);
		v[to].push_back(out + from);

		v[to + out].push_back(from);
		v[from].push_back(to + out);

		// out  <- > to
		c[out + from][to] = 1;
		c[to + out][from] = 1;
	}

	edmondkarp();

	printf("%d", ans);
	return 0;
}

6. 결과 사진

 

 

지적, 댓글 언제나 환영입니다~