알고리즘/알고리즘 이론, 템플릿

mcmf

b1ackhand 2024. 3. 7. 14:48
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <numeric>
#include <random>
#include <iostream>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

const int INF = 200000000;
const double pi = 3.14159265358979;
const ll MOD = 987654321;

int c[802][802];
int f[802][802];
int d[802][802];
vector<int> arr[802];
int N, M;
int n, a, b;
int cap;
int S = 0;
int D = 801;

pii mcmf(int source, int sink)
{
	int cnt = 0;
	int ret = 0;

	while (1) 
	{
		int prev[802];
		bool visited[802] = { 0, };
		int dist[802];

		queue<int> q;
		fill(prev, prev + 802, -1);
		fill(dist, dist + 802, INF);

		dist[S] = 0;
		visited[S] = true;

		q.push(S);

		//SPFA
		while (!q.empty())
		{
			int cur = q.front();
			q.pop();

			visited[cur] = false;

			for (int i = 0; i < arr[cur].size(); i++)
			{
				int next = arr[cur][i];
				if (c[cur][next] - f[cur][next] > 0 && dist[next] > dist[cur] + d[cur][next])
				{
					dist[next] = dist[cur] + d[cur][next];
					prev[next] = cur;
					if (!visited[next])
					{
						q.push(next);
						visited[next] = true;
					}
				}

			}
		}

		if (prev[D] == -1)
			break;

		int flow = INF;

		for (int i = D; i != S; i = prev[i])
			flow = min(flow, c[prev[i]][i] - f[prev[i]][i]);

		for (int i = D; i != S; i = prev[i])
		{
			ret += flow * d[prev[i]][i];
			f[prev[i]][i] += flow;
			f[i][prev[i]] -= flow;
		}

		cnt++;
	}

	return {cnt, ret};
}


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;

	rep1(i, N) 
	{
		c[S][i] = 1;
		arr[S].push_back(i);
		arr[i].push_back(S);
	}

	rep1(i, M)
	{
		c[i+400][D] = 1;
		arr[D].push_back(i+400);
		arr[i+400].push_back(D);
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 401; j <= 400 + M; j++) 
		{
			d[i][j] = INF;
		}
	}

	for (int i = 1; i <= N; i++) 
	{
		cin >> n;
		for (int j = 0; j < n; j++) 
		{
			cin >> a >> b;
			d[i][a + 400] = b;
			d[a + 400][i] = -b;

			arr[i].push_back(a + 400);
			arr[a + 400].push_back(i);
			c[i][a + 400] = 1;
		}
	}

	auto it = mcmf(S, D);

	cout << it.first << " " << it.second;

	return 0;
}

'알고리즘 > 알고리즘 이론, 템플릿' 카테고리의 다른 글

Atcoder ACL  (0) 2024.11.13
2-sat  (0) 2024.05.09
네트워크 플로우  (0) 2024.03.07
머지소트트리  (0) 2024.03.03
LCA , sparsetable  (0) 2023.12.11