Submit Info #41788

Problem Lang User Status Time Memory
Assignment Problem cpp golikovnik AC 1324 ms 12.39 MiB

ケース詳細
Name Status Time Memory
example_00 AC 3 ms 0.36 MiB
hand_minus_00 AC 712 ms 12.30 MiB
hand_plus_00 AC 1324 ms 12.39 MiB
max_random_00 AC 1046 ms 12.33 MiB
max_random_01 AC 1081 ms 12.30 MiB
max_random_02 AC 1089 ms 12.32 MiB
max_random_03 AC 1086 ms 12.33 MiB
max_random_04 AC 1091 ms 12.30 MiB
random_00 AC 49 ms 3.57 MiB
random_01 AC 62 ms 3.59 MiB
random_02 AC 8 ms 1.17 MiB
random_03 AC 61 ms 3.59 MiB
random_04 AC 0 ms 0.73 MiB

// Copyright 2021 Nikita Golikov #include <bits/stdc++.h> using namespace std; using i64 = int64_t; using ui64 = uint64_t; template <class A, class B> bool smin(A &x, B &&y) { if (y < x) { x = y; return true; } return false; } template <class A, class B> bool smax(A &x, B &&y) { if (x < y) { x = y; return true; } return false; } #include <bits/extc++.h> template <typename cap_t, typename flow_t, typename cost_t, typename dist_t> struct mcmf { struct edge { int from; int to; cap_t cap; cost_t cost; cap_t flow{}; edge(int from, int to, cap_t cap, cost_t cost) : from(from), to(to), cap(cap), cost(cost) {} bool ok() const { return flow < cap; } }; struct ans_t { flow_t flow; dist_t cost; }; dist_t const INF = numeric_limits<dist_t>::max() / 3; int n; vector<edge> edges; vector<vector<int>> graph; vector<dist_t> d; vector<int> par; vector<int> q; vector<char> in_q; vector<dist_t> pi; explicit mcmf(int n_) : n(n_), graph(n), d(n), par(n), in_q(n), pi(n) {} void add_edge(int from, int to, cap_t cap, cost_t cost) { graph[from].push_back((int) edges.size()); edges.emplace_back(from, to, cap, cost); graph[to].push_back((int) edges.size()); edges.emplace_back(to, from, 0, -cost); } void setPi(int s) { fill(pi.begin(), pi.end(), INF); pi[s] = 0; bool ch = true; while (ch) { ch = false; for (int v = 0; v < n; ++v) { for (int ei : graph[v]) { edge& e = edges[ei]; if (e.ok() && smin(pi[e.to], pi[v] + e.cost)) { ch = true; } } } } } ans_t solve(int source, int sink) { setPi(source); auto const MAX_FLOW = numeric_limits<flow_t>::max(); ans_t ans{}; auto expathDijkstra = [&] { fill(d.begin(), d.end(), INF); set<pair<dist_t, int>> st; st.emplace(0, source); d[source] = 0; while (!st.empty()) { auto[dv, v] = *st.begin(); st.erase(st.begin()); for (int ei : graph[v]) { edge& e = edges[ei]; auto nd = dv + pi[v] - pi[e.to] + e.cost; if (e.ok() && nd < d[e.to]) { st.erase({d[e.to], e.to}); d[e.to] = nd; st.emplace(nd, e.to); par[e.to] = ei; } } } for (int i = 0; i < n; ++i) { pi[i] = min(pi[i] + d[i], INF); } return d[sink] != INF; }; auto expathDijkstraPBDS = [&] { fill(d.begin(), d.end(), INF); __gnu_pbds::priority_queue<pair<i64, int>> st; vector<decltype(st)::point_iterator> its(n); st.push({0, source}); d[source] = 0; while (!st.empty()) { auto v = st.top().second; st.pop(); auto dv = d[v]; for (int ei : graph[v]) { edge& e = edges[ei]; auto nd = dv + pi[v] - pi[e.to] + e.cost; if (e.ok() && smin(d[e.to], nd)) { if (its[e.to] == st.end()) { its[e.to] = st.push({-nd, e.to}); } else { st.modify(its[e.to], {-nd, e.to}); } par[e.to] = ei; } } } for (int i = 0; i < n; ++i) { pi[i] = min(pi[i] + d[i], INF); } return d[sink] != INF; }; auto expath = [&] { fill(d.begin(), d.end(), INF); fill(in_q.begin(), in_q.end(), 0); q = {source}; int qh = 0; d[source] = 0; while (qh < (int) q.size()) { auto v = q[qh++]; in_q[v] = false; for (auto i : graph[v]) { auto const& e = edges[i]; auto u = e.to; if (e.ok() && smin(d[u], d[v] + e.cost)) { par[u] = i; if (!in_q[u]) { q.push_back(u); in_q[u] = true; } } } } return d[sink] != INF; }; while (expathDijkstraPBDS()) { flow_t push = MAX_FLOW; for (int cur = sink; cur != source; ) { auto const& e = edges[par[cur]]; smin(push, e.cap - e.flow); cur = e.from; } ans.flow += push; dist_t dcost = 0; for (int cur = sink; cur != source; ) { auto& e = edges[par[cur]]; e.flow += push; dcost += e.cost * push; edges[par[cur] ^ 1].flow -= push; cur = e.from; } ans.cost += dcost; } return ans; } }; int main() { #ifdef GOLIKOV assert(freopen("in", "rt", stdin)); auto _clock_start = chrono::high_resolution_clock::now(); #endif ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; mcmf<int, int, int, i64> graph(2 + 2 * n); for (int i = 0; i < n; ++i) { graph.add_edge(0, i + 1, 1, 0); graph.add_edge(n + i + 1 , 2 * n + 1, 1, 0); } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { int x; cin >> x; graph.add_edge(i + 1, n + j + 1, 1, x); } } cout << graph.solve(0, 2 * n + 1).cost << '\n'; vector<int> p(n); for (auto& e : graph.edges) { if (e.from > 0 && e.to < 2 * n + 1 && e.flow > 0) { p[e.from - 1] = e.to - n - 1; } } for (int x : p) cout << x << ' '; cout << '\n'; #ifdef GOLIKOV cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( chrono::high_resolution_clock::now() - _clock_start).count() << "ms." << endl; #endif return 0; }