Submit Info #54529

Problem Lang User Status Time Memory
Assignment Problem cpp 12tqian AC 211 ms 4.46 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.61 MiB
hand_minus_00 AC 211 ms 4.46 MiB
hand_plus_00 AC 206 ms 4.46 MiB
max_random_00 AC 89 ms 4.45 MiB
max_random_01 AC 85 ms 4.46 MiB
max_random_02 AC 86 ms 4.46 MiB
max_random_03 AC 91 ms 4.46 MiB
max_random_04 AC 88 ms 4.46 MiB
random_00 AC 11 ms 1.21 MiB
random_01 AC 13 ms 1.21 MiB
random_02 AC 3 ms 0.73 MiB
random_03 AC 14 ms 1.21 MiB
random_04 AC 1 ms 0.71 MiB

#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; /** * Another black box algorithm I don't understand * But I can use * O(N^2M) for N jobs and M workers * 0-indexed * Returns the cost, and the assignment * job stores the job each worker gets assigned to * In the example below, they wanted the worker each job got assigned to, so I inverted it */ 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; }