Submit Info #63600

Problem Lang User Status Time Memory
Assignment Problem cpp Lain AC 148 ms 2.40 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.45 MiB
hand_minus_00 AC 140 ms 2.32 MiB
hand_plus_00 AC 148 ms 2.39 MiB
max_random_00 AC 38 ms 2.32 MiB
max_random_01 AC 35 ms 2.39 MiB
max_random_02 AC 34 ms 2.40 MiB
max_random_03 AC 39 ms 2.36 MiB
max_random_04 AC 37 ms 2.36 MiB
random_00 AC 5 ms 0.70 MiB
random_01 AC 5 ms 0.70 MiB
random_02 AC 2 ms 0.45 MiB
random_03 AC 6 ms 0.76 MiB
random_04 AC 1 ms 0.45 MiB

#include "bits/stdc++.h" using namespace std; // Source: KACTL // Tested on: Hackerrank Inter-Hall Courier Service // Given a weighted bipartite graph, finds minimum weight matching. // Takes cost[n][m], where cost[i][j] = cost for L[i] to be matched with R[j] // returns {min cost, match} such that L[i] is matched with R[match[i]] // Negate costs for max cost. // Complexity is O(N^2M) template<typename T> pair<T,vector<int>> hungarian(const vector<vector<T>>& c) { if (c.empty()) return {0,{}}; int n = c.size()+1, m = c[0].size()+1; vector<T> u(n), v(m); vector<int> p(m), ans(n-1); for (int i = 1; i < n; i++) { p[0] = i; int j0 = 0; // Dummy worker 0 vector<T> dist(m,numeric_limits<T>::max()); vector<int> pre(m,-1); vector<char> done(m+1); do { // dijkstra done[j0] = 1; int i0 = p[j0], j1; T delta = numeric_limits<T>::max(); for (int j = 1; j < m; j++) { if (!done[j]) { auto curr = c[i0-1][j-1] - u[i0] - v[j]; if (curr < dist[j]) dist[j] = curr, pre[j] = j0; if (dist[j] < delta) delta = dist[j], j1 = j; } } for (int j = 0; j < m; j++) { 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; } } for (int j= 1; j < m; j++) { if (p[j]) ans[p[j]-1] = j-1; } return {-v[0],ans}; // min cost } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector<vector<int64_t>> a(n,vector<int64_t>(n)); for (int i =0; i < n; i++) { for (int j = 0; j < n; j++) cin >> a[i][j]; } auto [cost, perm] = hungarian(a); cout << cost << '\n'; for (auto& x : perm) cout << x << ' '; cout << '\n'; }