Submit Info #53514

Problem Lang User Status Time Memory
Assignment Problem cpp WeakestTopology AC 185 ms 2.60 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.71 MiB
hand_minus_00 AC 185 ms 2.59 MiB
hand_plus_00 AC 183 ms 2.59 MiB
max_random_00 AC 40 ms 2.58 MiB
max_random_01 AC 41 ms 2.59 MiB
max_random_02 AC 39 ms 2.58 MiB
max_random_03 AC 41 ms 2.58 MiB
max_random_04 AC 42 ms 2.60 MiB
random_00 AC 5 ms 0.95 MiB
random_01 AC 6 ms 0.95 MiB
random_02 AC 2 ms 0.71 MiB
random_03 AC 6 ms 0.96 MiB
random_04 AC 1 ms 0.71 MiB

#include <bits/stdc++.h> using namespace std; using ll = long long; template<typename T> struct Matching { T cost; // match[v] = matching row to column v (-1 if not matched) vector<int> match; vector<T> ldual, rdual; }; // returns maximum matching of minimum cost // assumes N <= M template<typename T> Matching<T> hungarian(const vector<vector<T>>& C) { static const T inf = numeric_limits<T>::max(); int N = (int)size(C), M = (int)size(C[0]); assert(N <= M); vector<int> match(M, -1); vector<T> ldual(N), rdual(M); for (int u = 0; u < N; ++u) { vector<T> dmin(M, inf); vector<int> best(M, -1); vector<bool> vis(M); int last = -1; for (int z = u; z != -1; z = match[last]) { T delta = inf; int next = -1; for (int v = 0; v < M; ++v) { if (vis[v]) continue; T d = C[z][v] - ldual[z] - rdual[v]; if (d < dmin[v]) { dmin[v] = d; best[v] = last; } if (dmin[v] < delta) { delta = dmin[v]; next = v; } } for (int v = 0; v < M; ++v) { if (vis[v]) { ldual[match[v]] += delta; rdual[v] -= delta; } else { dmin[v] -= delta; } } ldual[u] += delta; last = next; vis[last] = true; } for (int v = last; v != -1; v = best[v]) { match[v] = best[v] == -1 ? u : match[best[v]]; } } T cost = 0; for (int v = 0; v < M; ++v) { if (match[v] == -1) continue; cost += C[match[v]][v]; } return {cost, match, ldual, rdual}; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; vector<vector<ll>> A(N, vector<ll>(N)); for (int u = 0; u < N; ++u) { for (int v = 0; v < N; ++v) { cin >> A[v][u]; } } auto res = hungarian(A); cout << res.cost << '\n'; for (int u = 0; u < N; ++u) { int v = res.match[u]; cout << v << "\n "[u + 1 < N]; } exit(0); }