boj, 백준) 11408. 열혈강호 5 ( C/ C++ )

1. 문제 링크

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

11408번: 열혈강호 5

 

2. 문제 개요

직원이 N 명, 일이 M개가 있다. 모두 1번부터 N번, 1번부터 M번까지 번호가 매겨져 있다.

각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 함.

 

각각의 직원이 할 수 있는 일의 목록과 그 일을 할 때 지급해야 하는 월급이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지, 그리고 그때 강호가 지불해야 하는 월급의 최솟값을 구하는 프로그램을 작성하자.

 

 

3. 문제 힌트

MCMF 알고리즘을 적용하자.

 

4. 문제 풀이

값을 입력받을 때, 각 간선은 양방향 이어야 하고, Capacity는 단방향으로만 값을 넣어준다. (이문제에서는 1 , 최대 일을 1개 할 수 있으므로.)

비용은 정방향뿐만 아니라 역방향으로도 넣어주어야 한다. 역방향은 -부호를 붙여서 넣어준다.

 

MCMF알고리즘은 SPFA를 사용하여 Edmond karp 알고리즘보다 빠르게 최대 유량을 찾을 수 있다.

SPFA는 bellman ford 알고리즘에서 n-1번 모든 edge를 Relax 한다는것O(VE)과, Relax한 edge만 Queue에 삽입하여 다음 차례 때 Relax 해준다는 차이점이 있다.

 

SPFA를 통하여 최단 경로를 구하고, 그때의 최대 유량을 흘려보낸다.

전체 비용을 계산할 때는 간선의 비용을 더해주어야 한다.

 

이번 문제는 코드에 주석을 참고하여 한번 읽어보면 이해가 될 듯하다.

 

5. 코드

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int INF = 987654321, MAX_SIZE = 850;
const int src = 0, dest = 849, work = 400;

vector<int> adj_list[MAX_SIZE];
int c[MAX_SIZE][MAX_SIZE], f[MAX_SIZE][MAX_SIZE], pay[MAX_SIZE][MAX_SIZE];
int n, m, cnt, ans;

void mcmf()
{
	while (1)
	{
		int p[MAX_SIZE], d[MAX_SIZE];	//이전노드, src로부터의 최단거리
		fill(p, p + MAX_SIZE, -1);	//이전 정점은 모두 -1
		fill(d, d + MAX_SIZE, INF);	//거리는 자신을 제외한 모두 INF
		d[src] = 0;

		queue<int> q;
		bool inq[MAX_SIZE];	//Q안에 있는지 확인해야함. SPFA
		fill(inq, inq + MAX_SIZE, false);

		q.push(src);
		inq[src] = true;	//queue안에 있음을 의미
		p[src] = src;	//시작은 이전노드를 자기 자신으로 해두고

		while (!q.empty())
		{
			int cv = q.front(); q.pop();
			inq[cv] = false;

			int len = adj_list[cv].size();
			for (int i = 0; i < len; ++i)	//인접한 정점만 방문.
			{
				int nv = adj_list[cv][i];
				int nw = pay[cv][nv];
				//유량이 남아있고, 최단거리를 갱신할 수 있다면?
				if (c[cv][nv] - f[cv][nv] > 0 && d[nv] > d[cv] + nw)
				{
					d[nv] = d[cv] + nw;	//갱신하고
					p[nv] = cv;	//이전노드 설정하고
					if (!inq[nv])	//Queue안에 없다면
					{
						inq[nv] = true;	//queue에 있음을 표시하고 삽입.
						q.push(nv);
					}
				}
			}
		}
		//SPFA.. src에서 모든 정점으로 갈 수 있는 최단거리 구함.->d array
		if (p[dest] == -1)
			break;	//더이상의 최단경로가 없음. 종료조건

		int minflow = INF;
		for (int i = dest; i != src; i = p[i])
			minflow = min(minflow, c[p[i]][i] - f[p[i]][i]);
		//여유 용량중 가장 작은것이 흐르게 될것.
		
		for (int i = dest; i != src; i = p[i])
		{
			ans += minflow*pay[p[i]][i];	//유량과 ( 여기선 1) 월급을 곱함.
			
			f[p[i]][i] += minflow;	//정방향
			f[i][p[i]] += -minflow;	//역방향으로 바꿔주고..
		}
		
		//1명이 선택
		cnt++;

	}
	return;
}

int main()
{
	scanf("%d %d", &n, &m);
	//Src : 0 ... Dest : 849 .... Person : 1~400.... WORK: 401~800

	//src와 사람 연결
	for (int i = 1; i <= n; ++i)
	{
		c[src][i] = 1; // 용량은 순방향만 추가.

		adj_list[src].push_back(i);	//양방향 그래프
		adj_list[i].push_back(src);
	}
	//일과 dest 연결
	for (int i = 1; i <= m; ++i)
	{
		c[work+i][dest] = 1;

		adj_list[dest].push_back(i+work);
		adj_list[i+work].push_back(dest);
	}

	//사람과 일 연결
	for (int i = 1; i <= n; ++i)
	{
		int len;
		scanf("%d", &len);

		for (int j = 0; j < len; ++j)
		{
			int to, weight;
			scanf("%d %d", &to, &weight);

			adj_list[i].push_back(work+to);	//사람과 일도 양뱡향으로 연결
			adj_list[work + to].push_back(i);

			pay[i][work + to] = weight;	//간선의 비용은 양방향
			pay[work + to][i] = -weight;//반대로 갈 수 있으니 

			c[i][work + to] = 1;	//용량은 단방향.
		}
	}
	//-------complete making graph -----------


	mcmf();
	printf("%d\n%d\n", cnt, ans);
	return 0;
}

6. 결과 사진

 

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