Submit Info #67388

Problem Lang User Status Time Memory
Assignment Problem cpp Emilan AC 173 ms 2.40 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.45 MiB
hand_minus_00 AC 173 ms 2.32 MiB
hand_plus_00 AC 170 ms 2.40 MiB
max_random_00 AC 41 ms 2.32 MiB
max_random_01 AC 37 ms 2.40 MiB
max_random_02 AC 38 ms 2.36 MiB
max_random_03 AC 43 ms 2.40 MiB
max_random_04 AC 40 ms 2.32 MiB
random_00 AC 5 ms 0.70 MiB
random_01 AC 6 ms 0.77 MiB
random_02 AC 2 ms 0.45 MiB
random_03 AC 6 ms 0.70 MiB
random_04 AC 1 ms 0.45 MiB

#include <bits/stdc++.h> using namespace std; using ll = long long; #define sz(x) int((x).size()) #define rep(i, l, r) for (int i = (l); i < (r); i++) /** * Author: Benjamin Qi, chilli * Date: 2020-04-04 * License: CC0 * Source: https://github.com/bqi343/USACO/blob/master/Implementations/content/graphs%20(12)/Matching/Hungarian.h * Description: Given a weighted bipartite graph, matches every node on * the left with a node on the right such that no * nodes are in two matchings and the sum of the edge weights is minimal. Takes * cost[N][M], where cost[i][j] = cost for L[i] to be matched with R[j] and * returns (min cost, match), where L[i] is matched with * R[match[i]]. Negate costs for max cost. * Time: O(N^2M) * Status: Tested on yosupo's judge, kattis:cordonbleu, stress-tested */ using T = ll; pair<T, vector<int>> hungarian(const vector<vector<T>> &a) { if (a.empty()) return {0, {}}; int n = sz(a) + 1, m = sz(a[0]) + 1; vector<T> u(n), v(m); vector<int> p(m), ans(n - 1); rep(i,1,n) { p[0] = i; int j0 = 0; // add "dummy" worker 0 vector<T> dist(m, LLONG_MAX); // INT_MAX or LLONG_MAX vector<int> pre(m, -1); vector<bool> done(m + 1); do { // dijkstra done[j0] = true; int i0 = p[j0], j1; T delta = LLONG_MAX; // INT_MAX or LLONG_MAX rep(j,1,m) if (!done[j]) { T cur = a[i0 - 1][j - 1] - u[i0] - v[j]; if (cur < dist[j]) dist[j] = cur, pre[j] = j0; if (dist[j] < delta) delta = dist[j], j1 = j; } rep(j,0,m) { if (done[j]) u[p[j]] += delta, v[j] -= delta; else dist[j] -= delta; } j0 = j1; } while (p[j0]); while (j0) { // update alternating path int j1 = pre[j0]; p[j0] = p[j1], j0 = j1; } } rep(j,1,m) if (p[j]) ans[p[j] - 1] = j - 1; return {-v[0], ans}; // min cost } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<vector<ll>> cost(n, vector<ll>(n)); for (int u = 0; u < n; u++) { for (int v = 0; v < n; v++) { cin >> cost[u][v]; } } auto [ans, match] = hungarian(cost); cout << ans << "\n"; for (int u = 0; u < n; u++) { cout << match[u] << " \n"[u == n - 1]; } }