boj, 백준) 11378. 열혈강호 4 ( C / C++ )

1. 문제 링크

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

11378번: 열혈강호 4

2. 문제 개요

직원 N명 일 M개가 있다. 벌점을 X점 받은 사람은 일을 최대 X+1개 할 수 있다. 하지만 누가 X점을 받았는지는 모르고 저번 주에 받은 벌점의 합계는 안다. 적절히 배분해야 한다.

N, M, X가 주어 졌을 때 일을 최대 몇 개를 할 수 있는지 구하는 프로그램 작성.

 

3. 문제 힌트

최대 유량 알고리즘을 사용하기.

edmond karp algorithm.

 

 

4. 문제 풀이

일반 이분탐색

문제의 첫 번째 예시를 그림으로 나타내면 위의 그림과 같다.

이번 문제는 이분 탐색으로는 떠오르질 않아 다음과 같이 최대 유량 문제처럼 변경했다.

 

최대유량

기본적으로 모두 1개씩 할 수 있으므로 src부터 각 사람(1~5)까지 Link용량이 1인 간선을 연결. 일 M 역시 최대 M개까지 할 수 있으므로 sink와 Link용량이 1인 간선을 연결한다.

이제 기존의 문제와 다른 점은 bridge가 있다는 점이다.

만약에 벌점이 5점이고 1번이 3점, 5번이 2점이라고 한다면, src - bridge는 5의 용량, bridge - 1은 3의 용량, bridge - 5는 2의 용량 이런 식으로 했을 것이다.

하지만 총합만 알고 적절히 나눠가져야 하기 때문에 모두 X만큼 연결해주었다.

 

이 상태로 그래프를 만들어주고 src를 시작으로 최대 유량 알고리즘을 실행하면 정답을 알 수 있다.

 

5. 코드

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

//source, sink, bridge + 3;
vector<int> v[2010];
int n, m, k;
int src, dest, bridge;
int f[2010][2010];	//flow
int c[2010][2010];	//capacity
int ans = 0;

void edmondkarp()
{
	while (1)
	{
		queue<int> q;
		int p[2010] = { 0 }; // 이전 node
		fill(p, p + 2010, -1);

		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 = 0x7f7f7f7f;
		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])
		{
			f[p[i]][i] += minflow;
			f[i][p[i]] -= minflow;
		}
		ans += minflow;
	}
	return;
}

int main() 
{
	scanf("%d %d %d", &n, &m, &k);

	for (int i = 1; i <= n; ++i)
	{
		int t;
		scanf("%d", &t);
		for (int j = 0; j < t; ++j)
		{
			int val;
			scanf("%d", &val);
			v[i].push_back(val+1000);
			v[val + 1000].push_back(i);
			c[i][val+1000] = 1;
		}
	}

	src = 2001, dest = 2002, bridge = 2003;

	//용량은 없어도 경로는 양뱡향이여야함.

	//src와 bridge connect a line
	v[src].push_back(bridge);
	v[bridge].push_back(src);
	c[src][bridge] = k;

	//src,bridge와 n연결하기
	for (int i = 1; i <= n; ++i)
	{
		v[src].push_back(i);
		v[i].push_back(src);
		v[bridge].push_back(i);
		v[i].push_back(bridge);
		c[src][i] = 1;
		c[bridge][i] = k;
	}

	//m과 sink연결하기
	for (int i = 1001; i <= m+1000; ++i)
	{
		v[i].push_back(dest);
		v[dest].push_back(i);
		c[i][dest] = 1;
	}
	

	edmondkarp();

	printf("%d", ans);

	return 0;
}

6. 결과 사진

 

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