[백준] 17222 위스키 거래

문제

주은이와 명진이는 사적으로 위스키를 거래하는 사이이다. 주은이는 돈도 많고 위스키를 무척 좋아해서 위스키를 가능한 한 많이 사고 싶어하고, 명진이는 위스키가 넘쳐나서 위스키를 가능한 한 많이 팔고 싶다. 하지만 주은이 자신의 사회적 평판과 품위 때문에, 한 번에 너무 많은 양의 위스키를 직거래하는 것을 꺼려 한다. 그래서 주은이는 자신의 친구를 총동원하고 명진이에게도 은밀하게 부탁하여 사설 유통망을 구축해내기로 했다. 유통망의 구조는 다음과 같다.

• 주은이가 명진이에게 위스키를 주문한다.
• 명진이는 가능한 한 많은 위스키를 적절하게 분배하여 명진이의 친구들에게 발송한다.
• 명진이의 친구들은 자신의 연락망을 토대로 유통망 안에서 위스키를 주고받을 수 있다. 이들 중 몇몇은 주은이의 친구들과 연락할 수 있지만, 주은이와 직접 연락할 수는 없다.
• 명진이의 친구들에게서 위스키를 전달받은 주은이의 친구들은 모든 위스키를 주은이에게 전달한다.

명진이는 위스키를 무한하게 보낼 수 있고, 주은이 역시 친구들로부터 받을 수 있는 위스키의 양에 제한이 없다. 하지만 명진이와 주은이의 친구들도 각자의 사회적 평판을 걱정하기 때문에 각각 한 명에게서 전달받을 수 있는 양이 정해져 있다. 예를 들어 A가 한 번에 최대 5병의 위스키를 받을 수 있다면, A는 3명의 친구들로부터 위스키를 5병씩 전달받아서 주은이에게 총 15병을 전달할 수 있지만, 1명의 친구로부터 6병을 전달받지는 못한다.

각 친구들이 한 명에게서 최대 몇 병의 위스키를 전달받을 수 있는지, 명진이의 친구들이 누구에게 연락할 수 있는지에 대한 정보가 주어졌을 때, 주은이가 한 번에 최대 몇 병의 위스키를 받을 수 있을지를 구하여라.

입력

첫째 줄에 주은이의 친구들의 수 N과 명진이의 친구들의 수 M이 주어진다. (1 ≤ N, M ≤ 100)

둘째 줄에 주은이의 친구들이 한 명으로부터 전달받을 수 있는 최대 위스키의 양을 순서대로 입력한다. 이때 주은이의 친구들은 입력된 순서대로 1부터 N까지의 번호를 배정받는다.

셋째 줄에 명진이의 친구들이 한 명으로부터 전달받을 수 있는 최대 위스키의 양을 순서대로 입력한다. 이때 명진이의 친구들은 입력된 순서대로 N+1부터 N+M까지의 번호를 배정받는다.

한 명으로부터 전달받을 수 있는 최대 위스키의 양은 10,000,000을 넘지 않는다.

넷째 줄부터 M개의 줄에 걸쳐 명진이의 친구들이 각각 연락할 수 있는 사람들의 수 K와 그 리스트가 공백으로 구분되어 주어진다. (1 ≤ K ≤ N + M - 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;

int N, M, c[224][224], f[224][224], S = 201, E = 202, ca[201];
vi adj[224];
//S: 명진 E:주은

int main() {
	FAST;
	cin >> N >> M;
	REP(i, N) {
		cin >> ca[i];
		c[i][E] = INF;
		adj[i].push_back(E);
		adj[E].push_back(i);
	}
	for (int i = N + 1; i <= N + M; i++) {
		cin >> c[S][i];
		adj[S].push_back(i);
		adj[i].push_back(S);
		ca[i] = c[S][i];
	}
	int k;
	for (int i = N + 1; i <= N + M; i++) {
		cin >> k;
		while (k--) {
			int x;
			cin >> x;
			c[i][x] = ca[x];
			adj[i].push_back(x);
			adj[x].push_back(i);
		}
	}
	int total = 0;
	while (1) {
		queue<int>q;
		q.push(S);
		int p[224];
		memset(p, -1, sizeof(p));
		p[S] = S;
		while (!q.empty()) {
			int t = q.front();
			q.pop();
			for (int r : adj[t]) {
				if (p[r]==-1 && c[t][r] - f[t][r] > 0) {
					p[r] = t;
					q.push(r);
				}
			}
		}
		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;
		}
		total += flow;
	}
	cout << total;
}