Submit Info #47951

Problem Lang User Status Time Memory
Assignment Problem cpp brunovsky AC 434 ms 2.59 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.68 MiB
hand_minus_00 AC 388 ms 2.55 MiB
hand_plus_00 AC 362 ms 2.55 MiB
max_random_00 AC 434 ms 2.55 MiB
max_random_01 AC 434 ms 2.55 MiB
max_random_02 AC 431 ms 2.55 MiB
max_random_03 AC 432 ms 2.59 MiB
max_random_04 AC 434 ms 2.56 MiB
random_00 AC 27 ms 0.93 MiB
random_01 AC 33 ms 0.95 MiB
random_02 AC 5 ms 0.71 MiB
random_03 AC 32 ms 0.96 MiB
random_04 AC 3 ms 0.68 MiB

#include <bits/stdc++.h> using namespace std; // ***** template <typename Cost = long, typename CostSum = Cost> struct dense_mincost_hungarian { int U = 0, V = 0, W = 0, E = 0; bool padded = false; vector<vector<Cost>> cost; vector<int> m[2]; dense_mincost_hungarian() = default; dense_mincost_hungarian(int U, int V) : U(U), V(V), W(max(U, V)), cost(W, vector<Cost>(W, 0)) {} void set(int u, int v, Cost w) { assert(0 <= u && u < U && 0 <= v && v < V && w >= 0); cost[u][v] = w; } void pad_complete(Cost w) { assert(!padded), padded = true; for (int v = V; v < U; v++) // edges if padding V side for (int u = 0; u < U; u++) cost[u][v] = w; for (int u = U; u < V; u++) // edges if padding U side for (int v = 0; v < V; v++) cost[u][v] = w; } void pad_reverse() { assert(!padded), padded = true, W = U + V; cost.resize(W, vector<Cost>(W)); for (int u = 0; u < U; u++) for (int v = 0; v < V; v++) cost[v + U][u + V] = cost[u][v]; if (U <= V) { for (int v = 0; v < V; v++) cost[v + U][v] = 0; for (int u = 0; u < U; u++) cost[u][u + V] = cinf; } else { for (int u = 0; u < U; u++) cost[u][u + V] = 0; for (int v = 0; v < V; v++) cost[v + U][v] = cinf; } } vector<int> prev[2]; vector<CostSum> pi[2], dist[2]; static inline constexpr Cost cinf = numeric_limits<Cost>::max() / 3; static inline constexpr CostSum inf = numeric_limits<CostSum>::max() / 3; bool dijkstra() { dist[0].assign(W + 1, inf); dist[1].assign(W, inf); prev[0].assign(W + 1, -1); prev[1].assign(W, -1); for (int u = 0; u < W; u++) if (m[0][u] == W) dist[0][u] = 0; vector<bool> vis(W, false); for (int phase = 0; phase < W; phase++) { int u = -1; for (int v = 0; v < W; v++) { if (!vis[v] && (u == -1 || dist[0][v] < dist[0][u])) { u = v; } } assert(u != -1); vis[u] = true; for (int v = 0; v < W; v++) { int y = m[1][v]; CostSum relaxed = min(dist[0][u] + cost[u][v] + pi[0][u] - pi[1][v], inf); if (dist[0][y] > relaxed) { dist[0][y] = relaxed, prev[0][y] = v; } if (dist[1][v] > relaxed) { dist[1][v] = relaxed, prev[1][v] = u; } } } reprice(); return prev[0][W] != -1; } void reprice() { for (int i : {0, 1}) { for (int u = 0; u < W; u++) { pi[i][u] = min(dist[i][u] + pi[i][u], inf); } } } auto path() const { vector<array<int, 2>> nodes; int v = prev[0][W]; while (v != -1) { nodes.push_back({prev[1][v], v}); v = prev[0][prev[1][v]]; } return nodes; } auto mincost_max_matching(bool include_padding = false) { assert(U == V || padded); m[0].assign(W, W); m[1].assign(W, W); pi[0].assign(W, 0); pi[1].assign(W, 0); int matches = 0; while (matches < W && dijkstra()) { for (auto [u, v] : path()) { m[0][u] = v, m[1][v] = u; } matches++; } if (matches < W) { // return CostSum(-1); } CostSum min_cost = 0; for (int u = 0; u < W; u++) { int v = m[0][u]; assert(0 <= v && v < W); if (include_padding || (u < U && v < V)) { min_cost += cost[u][v]; } } return min_cost; } }; #define MAXA 1'000'000'000L auto solve() { int N; cin >> N; dense_mincost_hungarian<long, long> mch(N, N); for (int u = 0; u < N; u++) { for (int v = 0; v < N; v++) { long a; cin >> a; a += MAXA; mch.set(u, v, a); } } long ans = mch.mincost_max_matching(); ans -= N * MAXA; cout << ans << endl; for (int u = 0; u < N; u++) { cout << mch.m[0][u] << " \n"[u + 1 == N]; } } // ***** int main() { ios::sync_with_stdio(false); solve(); return 0; }