백준 - 11375 열혈강호

  본 문제를 풀수 있는 방법은 여러가지가 있을 수 있겠지만 그중 한가지 방법은 본 문제를 네트워크 유량의 구조로 모델링을 잘 하는데 있다.

네트워크 유량 이량 그래프에서 source 와 sink 의 weight 가 주어졌을때 임의의 두 노드 사이에 흐를 수 있는 weight 의 최대치를 계산하는 알고리즘이다.

사실 네트워크 플로우의 최대 유량을 계산하는 알고리즘을 이해하는 것은 만만치 않은 일이기 때문에 본 폐이지에서는 대표적인 최대 유량 알고리즘 인 에드몬드-카프 알고리즘을 구현한 C++ Class 를 도입하고 이를 활용하여 답을 찾는데 주안점을 둘 것이다. 해당 클래스의 사용법을 이해하고 재활용하면 여러가지 다양한 최대유량 알고리즘을 손쉽게 풀수 있을 것이다.

  문제로 돌아가서 본 문제의 네트워크 플로우를 모델링 하자면 아래의 그림과 같다.

 

한명의 직원이 1개의 일만 할 수 있기 때문에 source 에서 worker 로 이어지는 간선의 weight 는 1 이다.

만약 각 worker 가 할수 있는 일이 복수개라면 해당 간선의 weight 를 조절해 주면 된다.

worker 와 job 사이 및 job 에서 sink 로 이어지는 간선의  weight 는 모두 1로 맞추면 된다.

  우리가 해야 할일은 에드 몬드 카프 알고리즘으로 구현된 클래스에 각 node 간 weight 를 세팅한 후 source 에서 sink 노드로 최대유량이 얼마인지 쿼리하는 일이다.

소스코드는 아래와 같다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct NetworkFlow
{
	const int INF = 1 << 30;
	int nrNode;
	vector<vector<int>> c;
	vector<vector<int>> f;
	vector <vector<int>> v;
	vector<int> parent;
	NetworkFlow(int n) : nrNode(n)
	{
		parent.resize(nrNode);
		c.resize(nrNode);

		for (int i = 0; i < nrNode; i++)
		{
			c[i].resize(nrNode);
			fill(c[i].begin(), c[i].end(), 0);
		}
		f = c;

		v.resize(nrNode);
	}
	int residual(int here, int there)
	{
		return c[here][there] - f[here][there];
	}

	int min2(int a, int b) {
		return (a > b) ? b : a;
	}

	int edmonds_karp(int source, int sink) {
		int total = 0;
		while (true) {
			fill(parent.begin(), parent.end(), -1);
			queue<int> Q;
			Q.push(source);
			parent[source] = source;
			while (!Q.empty() && parent[sink] == -1) {
				int here = Q.front();
				Q.pop();
				for (int there : v[here]) {
					if (residual(here, there) > 0 && parent[there] == -1) {
						parent[there] = here;
						Q.push(there);
					}
				}
			}

			if (parent[sink] == -1) break;

			int mn = INF;
			for (int p = sink; p != source; p = parent[p]) {
				mn = min2(c[parent[p]][p] - f[parent[p]][p], mn);
			}

			for (int p = sink; p != source; p = parent[p]) {
				f[parent[p]][p] += mn;
				f[p][parent[p]] -= mn;
			}
			total += mn;
		}
		return total;
	}
	void SetFlow(int src, int sink, int weight)
	{
		v[src].push_back(sink);
		v[sink].push_back(src);
		c[src][sink] = weight;
	}

};

int main()
{
	int n_w, n_j;

	cin >> n_w >> n_j;

	NetworkFlow nf(n_w + n_j + 2);

	for (int i = 0; i < n_w; i++)
	{
		int job;
		cin >> job;
		nf.SetFlow(0, i + 1, 2);
		for (int j = 0; j < job; j++)
		{
			int tmp;
			cin >> tmp;

			nf.SetFlow(i + 1, tmp + n_w, 1);
		}
	}
	for (int j = 0; j < n_j; j++)
	{
		nf.SetFlow(j + n_w + 1, n_w + n_j + 1, 1);
	}

	cout << nf.edmonds_karp(0, n_w + n_j + 1) << endl;
}

 

총노드의 개수는 worker + job + 2 이다. source 와 sink 노드가 추가로 필요하기 때문이다.

source node 의 번호는 0 이며 N 개의 worker 가 번호매겨지고, M 개의 job 이 번호 매겨진다. 맨마지막 sink node 의 번호가 부여된다.