verify/yosupo/yosupo-assignment.test.cpp

View this file on GitHub
Last update: 2022-07-21 16:12:33-04:00
Problem: https://judge.yosupo.jp/problem/assignment

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/assignment"

#include "../../library/contest/template-minimal.hpp"
#include "../../library/graphs/flows/hungarian.hpp"

int main() {
	int n; cin >> n;
	vector<vector<long long>> a(n, vector<long long>(n));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) cin >> a[i][j];
	auto res = hungarian(a);
	vector<int> loc(n);
	for (int i = 0; i < n; i++) {
		loc[res.second[i]] = i;
	}
	cout << res.first << '\n';
	for (int x : loc) 
		cout << x << " ";
	cout << '\n';
	return 0;
}

#define PROBLEM "https://judge.yosupo.jp/problem/assignment"


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

template <class C> std::pair<C, std::vector<int>> hungarian(const std::vector<std::vector<C>>& a_) {
	const C INF = std::numeric_limits<C>::max();
	int n = (int)a_.size();
	int m = (int)a_[0].size();
	assert(n <= m);
	std::vector<std::vector<C>> a(n + 1, std::vector<C>(m + 1, 0));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			a[i + 1][j + 1] = a_[i][j];
	std::vector<C> u(n + 1), v(m + 1);
	std::vector<int> job(m + 1);
	for (int i = 1; i <= n; i++) {
		int w = 0;
		job[w] = i;
		std::vector<C> dist(m + 1, INF);
		std::vector<int> pre(m + 1, -1);
		std::vector<bool> done(m + 1);
		while (job[w]) {
			done[w] = 1;
			int j = job[w], nxt;
			C delta = INF;
			for (int ww = 0; ww <= m; ww++) {
				if (!done[ww]) {
					if (dist[ww] > a[j][ww] - u[j] - v[ww]) {
						dist[ww] = a[j][ww] - u[j] - v[ww];
						pre[ww] = w; 
					}
					if (delta > dist[ww]) {
						delta = dist[ww];
						nxt = ww;
					}
				}
			}
			for (int ww = 0; ww <= m; ww++) {
				if (done[ww]) {
					u[job[ww]] += delta;
					v[ww] -= delta;
				} else {
					dist[ww] -= delta;
				}
			}
			w = nxt;
		}
		for (int ww; w; w = ww) 
			job[w] = job[ww = pre[w]];
	}
	job.erase(job.begin());
	for (int i = 0; i < m; i++)
		job[i]--;
	return {-v[0], job};
}

int main() {
	int n; cin >> n;
	vector<vector<long long>> a(n, vector<long long>(n));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) cin >> a[i][j];
	auto res = hungarian(a);
	vector<int> loc(n);
	for (int i = 0; i < n; i++) {
		loc[res.second[i]] = i;
	}
	cout << res.first << '\n';
	for (int x : loc) 
		cout << x << " ";
	cout << '\n';
	return 0;
}