[백준] 2367 파티 +에드먼드 카프 알고리즘

문제

N(3 ≤ N ≤ 200)명의 사람이 파티를 하려고 한다. 각각의 사람은 몇 종류의 음식을 요리할 줄 안다. 각각의 음식의 종류는 1부터 D(5 ≤ D ≤ 100)까지의 정수로 표현된다 하자. 파티를 위해서 각각의 사람이 요리를 해서 가져오기로 했는데, 가급적이면 많은 양(접시의 수로 계산)의 음식을 파티에 준비하려 한다.

그렇다면 각각의 음식을 최대한 많이 준비해 오면 되겠지만, 우선 각각의 사람이 가져올 수 있는 음식의 양에 제한이 있다. 각각의 사람은 최대 K(1 ≤ K ≤ 5)개의 접시밖에 가져올 수 없다고 하자. 이때 같은 종류의 음식은 한 접시밖에 가져갈 수 없다고 하자. 즉, 한 사람이 세 접시의 스테이크를 가져올 수 없지만, 한 접시의 스테이크, 한 접시의 샐러드, 한 접시의 파스타를 가져올 수 있다.

또한 각 음식의 종류마다도 가져올 수 있는 양에 제한이 있다. 사전에 파티 참석자들에게 음식 선호도 조사를 하여 낭비되는 음식이 없도록 양을 정했다.

이와 같은 제한들이 주어졌을 때, 파티에 준비될 수 있는 접시(물론 음식이 담겨있는)의 개수의 최댓값을 알아내는 프로그램을 작성하시오.

 

입력

첫째 줄에는 N, K, D가 주어진다. 다음 줄에는 D개의 정수가 주어지는데, 이는 각 음식의 종류마다 가져올 수 있는 양의 제한을 의미한다. 이 값은 N보다 작거나 같은 음이 아닌 정수이다. 다음 N개의 줄에는 각 사람이 요리할 줄 아는 음식의 종류 개수 Z(1 ≤ Z ≤ D)와, Z개의 정수로 요리할 줄 아는 음식의 번호가 주어진다.

출력

첫째 줄에 파티에 준비될 수 있는 접시 개수의 최댓값을 출력한다.

 

 

이분그래프로 모델링이 가능합니다.

소스에서 사람으로 capacity 는 K이고,

음식에서 싱크로 capacity는 입력받습니다.

그리고 한사람이 한종류의 음식은 하나밖에 가져가지 못하므로, capacity는 1입니다.

 

에드먼즈 알고리즘으로 해결이 가능합니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;

using namespace std;
int N, K, D, c[303][303], f[303][303], S = 301, E = 302, x, y, ans;
vi adj[303];
//1~200: 사람
//201~300: 음식
//301:소스
//302:싱크
int main() {
	FAST;
	cin >> N >> K >> D;
	for (int i = 201; i <= 200 + D; i++) {
		cin>>c[i][E];
		adj[i].push_back(E);
		adj[E].push_back(i);
	}
	REP(i, N) {
		adj[S].push_back(i);
		adj[i].push_back(S);
		c[S][i] = K;
		cin >> x;
		while (x--) {
			cin >> y;
			adj[i].push_back(y+200);
			adj[y+200].push_back(i);
			c[i][y+200] = 1;
		}
	}
	//에드먼즈
	while (1) {
		queue<int>q;
		q.push(S);
		int p[303];
		fill(p, p + 303, -1);
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			for (int nxt : adj[cur]) {
				if (p[nxt] == -1 && c[cur][nxt] - f[cur][nxt] > 0) {
					p[nxt] = cur;
					q.push(nxt);
				}
			}
		}
		if (p[E] == -1)break;
		int flow = INF;
		for (int i = E; i != S; i = p[i]) {
			flow = min(flow, c[p[i]][i] - f[p[i]][i]);
		}
		for (int i = E; i != S; i = p[i]) {
			f[p[i]][i] += flow;
			f[i][p[i]] -= flow;
		}
		ans += flow;
	}
	cout << ans;
}