[백준] 11408 열혈강호 5

문제

강호네 회사에는 직원이 N명이 있고, 해야 할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다.

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

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

입력

첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 400)

둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호와 그 일을 할 때 지급해야 하는 월급이 주어진다. 월급은 10,000보다 작거나 같은 자연수 또는 0이다.

출력

 

첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.

둘째 줄에는 강호가 지급해야 하는 월급의 최솟값을 출력한다.

 

 

Minimum Cost Maximum flow 문제입니다.

각 간선의 capacity는 1 입니다.

따라서 flow는 최대 1밖에 될 수 없습니다.

직원>>일 로 가는 cost는 주어지지만, source에서 직원으로, 일에서 sink로 가는 cost는 항상 0입니다

따라서 MCMF를 이용해서 가장 적은 비용이 드는 간선으로 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 };
int N, M, S = 801, E = 802;
int c[803][803], f[803][803], cost[803][803], n, a, b, INF = 987654321, ans, cnt;
vi adj[803];
//1~400 : 사람  401~800 : 일 801:소스 802:싱크
int main() {
	FAST;
	cin >> N >> M;
	REP(i, N) {
		c[S][i] = 1;
		adj[i].push_back(S);
		adj[S].push_back(i);
	}
	for (int i = 401; i <= 400 + M; i++) {
		c[i][E] = 1;
		adj[i].push_back(E);
		adj[E].push_back(i);
	}
	REP(i, N) {
		cin >> n;
		while (n--) {
			cin >> a >> b;
			adj[i].push_back(400 + a);
			adj[400 +a].push_back(i);
			cost[i][400+a] = b;
			cost[400+a][i] = -b;
			c[i][400 + a] = 1;
		}
	}

	while (1) {
		int parent[803], dist[803], inQ[803];
		mset(inQ);
		fill(dist, dist + 803, INF);
		fill(parent, parent + 803, -1);
		queue<int>q;
		q.push(S);
		dist[S] = 0;
		inQ[S] = 1;
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			inQ[cur] = 0;
			for (auto next : adj[cur]) {
				if (c[cur][next]-f[cur][next] > 0 && dist[next] > dist[cur] + cost[cur][next]) {
					dist[next] = dist[cur] + cost[cur][next];
					parent[next] = cur;
					if (!inQ[next]) {
						inQ[next] = 1;
						q.push(next);
					}
				}
			}
		}
		if (parent[E] == -1) {
			break;
		}
		int flow = 1;
		for (int i = E; i != S; i = parent[i]) {
			f[parent[i]][i] = flow;
			f[i][parent[i]] = -flow;
			ans += cost[parent[i]][i];
		}
		cnt++;
	}
	cout <<cnt<<"\n"<< ans;
}