[BOJ] 백준 11408번: 열혈강호 5

MCMF (minimum cost maximum flow) 알고리즘을 사용하는 문제.

할 수 있는 일을 매칭하기 위하여 NF (Network Flow) 를 수행, 이 때 최소 비용을 구하기 위하여 SPFA + SLF 수행

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;
int n, m;
int ca[802][802];
int fl[802][802];
int cost[802][802];
int S = 0, D = 801;
vector<int> v[802];
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		ca[S][i] = 1;
		v[S].push_back(i);
		v[i].push_back(S);
	}
	for (int i = 1; i <= m; i++) {
		ca[i + 400][D] = 1;
		v[D].push_back(i + 400);
		v[i+400].push_back(D);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 401; j <= 400 + m; j++) {
			cost[i][j] = 2e9;
		}
	}
	for (int i = 1; i <= n; i++) {
		int num;
		cin >> num;
		for (int j = 0; j < num; j++) {
			int w, mo;
			cin >> w >> mo;
			cost[i][w + 400] = mo;
			cost[w+400][i] = -mo;
			v[i].push_back(w + 400);
			v[w + 400].push_back(i);
			ca[i][w + 400] = 1;
		}
	}
	int ans = 0;
	int result = 0;
	while (1) {
		int pre[802];
		bool visit[802] = { 0, };
		int dist[802];
		fill(dist, dist + 802, 2e9);
		fill(pre, pre + 802, -1);
		deque<int> q;
		q.push_back(S);
		dist[S] = 0;
		visit[S] = true;
		while (!q.empty()) {
			int node = q.front(); q.pop_front();
			visit[node] = false;
			
			for (auto nxt : v[node]) {
				if (dist[nxt] > dist[node] + cost[node][nxt] && ca[node][nxt] > fl[node][nxt]) {
					dist[nxt] = dist[node] + cost[node][nxt];
					pre[nxt] = node;
					if (!visit[nxt]) {
						visit[nxt] = 1;
						q.push_back(nxt);
						if (dist[q.front()] > dist[q.back()]) {
							q.push_front(q.back());
							q.pop_back();
						}
					}
				}
			}
		}
		if (pre[D] == -1) {
			break;
		}
		int flow = 2e9;
		for (int i = D; i != S; i = pre[i]) {
			flow = min(flow, ca[pre[i]][i] - fl[pre[i]][i]);
		}
		for (int i = D; i != S; i = pre[i]) {
			result += cost[pre[i]][i];
			fl[pre[i]][i] += flow;
			fl[i][pre[i]] -= flow;
		}
		ans += flow;
	}
	cout << ans << "\n" << result << "\n";
}