BOJ 백준 2316 : 도시 왕복하기 2

시작하면서

　이번 문제는 네트워크 유량/최대 유량(Network Flow) 과 관련된 문제이다.

BOJ 2316 - 도시 왕복하기 2

​

문제 이해

​ 네트워크 유량/최대 유량(Network Flow) 문제는 포드-풀커슨 알고리즘(Ford-Fulkerson)/에드몬드-카프 알고리즘(Edmonds-Karp Algorithm) 으로 해결할 수 있다. 개념은 해당 블로그를 참조하도록 한다.

​ 이 문제는 앞에서 풀었던 도시 왕복하기 1 문제의 확장판이다. 문제에서 중요하게 봐야할 점은 다음 조건들이다.

1. 한 도시를 두 번 이상 방문하지 않아야 함
2. 한 개 이상의 도시를 중간에 거쳐야 함

​ 1번 조건을 충족하기 위해, 한 정점을 들어오는 in 정점, out 정점 2개로 나누어서 용량 1의 간선으로 연결한다. 그리고 마을과 마을을 이을 때에는 out->in, in->out 방향으로 용량 1의 간선을 이어서 문제를 해결한다.

​

해결

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <limits.h>

using namespace std;

#define MAX_SIZE (801)

int DoEdmondKarp(const vector<vector<int> >& graph, const vector<vector<int> >& capacity, const int kOutIndex)
{
	const int kSource = 401;
	const int kSink = 2;

	vector<vector<int> > flow(MAX_SIZE);
	for (int i = 1; i < flow.size(); i++)
	{
		flow[i].resize(MAX_SIZE);
	}

	int result = 0;
	while (true)
	{
		vector<int> p(MAX_SIZE, -1);
		p[kSource] = kSource;

		queue<int> queue;
		queue.push(kSource);

		while (queue.empty() == false)
		{
			int current = queue.front(); queue.pop();

			for (int i = 0; i < graph[current].size(); i++)
			{
				int next = graph[current][i];

				if (capacity[current][next] - flow[current][next] > 0 && p[next] == -1)
				{
					p[next] = current;
					queue.push(next);

					if (next == kSink)
					{
						break;
					}
				}
			}
		}

		if (p[kSink] == -1)
		{
			break;
		}

		int minimumFlow = INT_MAX;
		for (int i = kSink; i != kSource; i = p[i])
		{
			minimumFlow = min(minimumFlow, capacity[p[i]][i] - flow[p[i]][i]);
		}

		for (int i = kSink; i != kSource; i = p[i])
		{
			flow[p[i]][i] += minimumFlow;
			flow[i][p[i]] -= minimumFlow;
		}

		result += minimumFlow;
	}

	return result;
}


int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// sync off

	vector<vector<int> > graph;
	vector<vector<int> > capacity;
	int N, P;

	cin >> N >> P;

	const int kOutIndex = 400;
	capacity.resize(MAX_SIZE);
	for (int i = 1; i <= capacity.size(); i++)
	{
		capacity[i].resize(MAX_SIZE);
	}

	graph.resize(801);
	for (int i = 1; i <= N; i++)
	{
		graph[i].push_back(kOutIndex + i);
		graph[kOutIndex + i].push_back(i);

		capacity[i][kOutIndex + i] = 1;
	}

	const int kCapacity = 1;
	for (int i = 0; i < P; i++)
	{
		int from, to;
		cin >> from >> to;

		graph[from + kOutIndex].push_back(to);
		graph[to].push_back(from + kOutIndex);

		graph[to + kOutIndex].push_back(from);
		graph[from].push_back(to + kOutIndex);

		capacity[from + kOutIndex][to] = kCapacity;
		capacity[to + kOutIndex][from] = kCapacity;
	}

	cout << DoEdmondKarp(graph, capacity, kOutIndex);

	return 0;
}