BOJ 백준 17412 : 도시 왕복하기 1

시작하면서

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

BOJ 17412 - 도시 왕복하기 1

​

문제 이해

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

​ 이 문제는 별 다른 아이디어 없이, 알고리즘을 구현해서 그대로 사용하면 문제가 해결된다.

​

해결

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

using namespace std;

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

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

	int result = 0;
	while (true)
	{
		vector<int> parent(graph.size(), -1);
		parent[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 && parent[next] == -1)
				{
					parent[next] = current;
					queue.push(next);

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

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

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

		for (int i = kSink; i != kSource; i = parent[i])
		{
			flow[parent[i]][i] += minimumFlow;
			flow[i][parent[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;

	capacity.resize(N + 1);
	for (int i = 1; i <= N; i++)
	{
		capacity[i].resize(N + 1);
	}

	graph.resize(N + 1);
	for (int i = 0; i < P; i++)
	{
		int from, to;
		cin >> from >> to;

		graph[from].push_back(to);
		graph[to].push_back(from);
		capacity[from][to] = 1;
	}

	cout << DoEdmondKarp(graph, capacity);

	return 0;
}