Submit Info #59704

Problem Lang User Status Time Memory
Assignment Problem cpp Felerius AC 1785 ms 21.20 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.45 MiB
hand_minus_00 AC 1114 ms 13.40 MiB
hand_plus_00 AC 1785 ms 21.20 MiB
max_random_00 AC 552 ms 13.44 MiB
max_random_01 AC 557 ms 13.41 MiB
max_random_02 AC 555 ms 13.41 MiB
max_random_03 AC 551 ms 13.47 MiB
max_random_04 AC 553 ms 13.43 MiB
random_00 AC 35 ms 2.70 MiB
random_01 AC 44 ms 3.04 MiB
random_02 AC 6 ms 1.07 MiB
random_03 AC 41 ms 2.97 MiB
random_04 AC 1 ms 0.45 MiB

#pragma GCC optimize("fast-math") // begin "cp-lib/prelude.hpp" #include <bits/stdc++.h> #ifdef LOCAL # include <dbg.h> #else # define dbg(...) do {} while (0) #endif #define cp_lib_4th(_1, _2, _3, x, ...) x #define cp_lib_rep(i, l, r) for (int i = (l); (i) < (r); ++(i)) #define cp_lib_rep0(i, r) cp_lib_rep(i, 0, r) #define rep(...) cp_lib_4th(__VA_ARGS__, cp_lib_rep, cp_lib_rep0, _)(__VA_ARGS__) #define cp_lib_repr(i, r, l, ...) for (int i = (r); (i) >= (l); --(i)) #define repr(...) cp_lib_repr(__VA_ARGS__, 0) #define all(a) ::begin(a),::end(a) #define trav(a, b) for (auto&& a : (b)) using namespace std; using ll = long long; using ld = long double; [[maybe_unused]] static constexpr int INF = int(1e9 + 5); [[maybe_unused]] static constexpr ll INFL = ll(INF) * INF; template <class C> int sz(const C& c) { return int(::size(c)); } // end "cp-lib/prelude.hpp" // begin "cp-lib/graph/flow/capacity-scaling.hpp" // begin "_detail.hpp" template <class Flow> struct FlowEdge { int to, rev; Flow rem_cap, cap; Flow flow() const { return cap - rem_cap; } }; template <class Flow, class Cost> struct CostFlowEdge : FlowEdge<Flow> { Cost cost; }; namespace cp_lib_flow { template <class Flow, class Cost = void> struct FlowGraph { static_assert(is_signed_v<Flow> && (is_void_v<Cost> || is_signed_v<Cost>)); using Edge = conditional_t<is_void_v<Cost>, FlowEdge<Flow>, CostFlowEdge<Flow, Cost>>; vector<vector<Edge>> adj; explicit FlowGraph(int n) : adj(n) {} Flow calc_flow(int s, int t, Flow limit = numeric_limits<Flow>::max()); vector<pair<Flow, vector<Edge*>>> decompose(int s, int t); vector<bool> calc_cut(int s); }; } // end "_detail.hpp" template <class Flow = ll, class Cost = ll, Flow Scale = 4> struct CapacityScalingFlowGraph : cp_lib_flow::FlowGraph<Flow, Cost> { using Base = cp_lib_flow::FlowGraph<Flow, Cost>; using Base::Base; Flow max_cap{0}; int add_edge(int s, int t, Flow cap, Cost cost) { int idx = sz(Base::adj[s]), idx_rev = (s == t ? idx + 1 : sz(Base::adj[t])); Base::adj[s].push_back(typename Base::Edge{{t, idx_rev, cap, cap}, cost}); Base::adj[t].push_back(typename Base::Edge{{s, idx, Flow(0), Flow(0)}, -cost}); max_cap = max(max_cap, abs(cap)); return idx; } template <class TotalCost = ll> optional<pair<TotalCost, vector<Cost>>> minimize_circulation(vector<Flow> excess = {}) { int n = sz(Base::adj); vector<int> with_excess, seen; vector<Cost> pi(n), dist(n); vector<typename Base::Edge*> back(n); Flow delta = max_cap; if (!sz(excess)) excess.resize(n, Flow(0)); auto push = [&](typename Base::Edge& e, Flow amt) { e.rem_cap -= amt; Base::adj[e.to][e.rev].rem_cap += amt; }; auto push_flow = [&](int s) { priority_queue<pair<Cost, int>> q; q.emplace(Cost(0), s); fill(all(dist), numeric_limits<Cost>::max()); dist[s] = Cost(0); seen.clear(); while (sz(q) && excess[q.top().second] > -delta) { auto [d, v] = q.top(); q.pop(); d = -d; if (d > dist[v]) continue; seen.push_back(v); d += pi[v]; trav(e, Base::adj[v]) { auto new_dist = d + e.cost - pi[e.to]; if (e.rem_cap < delta || new_dist >= dist[e.to]) continue; dist[e.to] = new_dist; q.emplace(-new_dist, e.to); back[e.to] = &Base::adj[e.to][e.rev]; } } if (!sz(q)) return false; auto [dt, t] = q.top(); dt = -dt; trav(v, seen) pi[v] += dist[v] - dt; Flow f = -excess[t]; for (int v = t; v != s; v = back[v]->to) f = min(f, Base::adj[back[v]->to][back[v]->rev].rem_cap); f = min(f, excess[s]); f -= f % delta; for (int v = t; v != s; v = back[v]->to) push(*back[v], -f); excess[s] -= f; excess[t] += f; return true; }; for (; delta; delta = (Flow(1) < delta && delta < Scale ? Flow(1) : delta / Scale)) { with_excess.clear(); rep(v, n) trav(e, Base::adj[v]) { auto cap = e.rem_cap - e.rem_cap % delta; if (cap < 0 || pi[v] + e.cost - pi[e.to] < 0) push(e, cap), excess[v] -= cap, excess[e.to] += cap; } rep(v, n) if (excess[v] > 0) with_excess.push_back(v); trav(v, with_excess) while (excess[v] >= delta && push_flow(v)); } TotalCost cost{0}; rep(v, n) { if (excess[v]) return {}; trav(e, Base::adj[v]) cost += TotalCost(e.flow()) * TotalCost(e.cost); } return pair(cost / 2, move(pi)); } }; // end "cp-lib/graph/flow/capacity-scaling.hpp" // begin "cp-lib/graph/flow/cost-scaling.hpp" template <class Flow = ll, class Cost = ll, Cost Alpha = 16> struct CostScalingFlowGraph : cp_lib_flow::FlowGraph<Flow, Cost> { using Base = cp_lib_flow::FlowGraph<Flow, Cost>; using Base::Base; Cost max_cost = 0; int add_edge(int s, int t, Flow cap, Cost cost) { int idx = sz(Base::adj[s]), idx_rev = (s == t ? idx + 1 : sz(Base::adj[t])); auto scaled_cost = cost * Cost(Alpha) * Cost(sz(Base::adj)); Base::adj[s].push_back(typename Base::Edge{{t, idx_rev, cap, cap}, scaled_cost}); Base::adj[t].push_back(typename Base::Edge{{s, idx, Flow(0), Flow(0)}, -scaled_cost}); max_cost = max(max_cost, abs(scaled_cost)); return idx; } template <class TotalCost = ll> TotalCost minimize_circulation(vector<Flow> excess = {}) { int n = sz(Base::adj); vector<Cost> pi(n); vector next(n, 0); vector<uint8_t> inq(n); queue<int> q; auto eps = max_cost; if (!sz(excess)) excess.resize(n, Flow(0)); auto push = [&](typename Base::Edge& e, Flow f) { auto& rev = Base::adj[e.to][e.rev]; e.rem_cap -= f; rev.rem_cap += f; excess[e.to] += f; excess[rev.to] -= f; }; auto relabel = [&](int v) { auto mx = numeric_limits<Cost>::min(); trav(e, Base::adj[v]) if (e.rem_cap) mx = max(mx, pi[e.to] - e.cost); pi[v] = mx - eps; next[v] = 0; }; for (; eps; eps = (Cost(1) < eps && eps < Alpha ? Cost(1) : eps / Alpha)) { fill(all(next), 0); rep(v, n) trav(e, Base::adj[v]) if (pi[v] + e.cost - pi[e.to] < 0 && e.rem_cap) push(e, e.rem_cap); rep(v, n) if (excess[v] > 0) q.push(v), inq[v] = true; while (sz(q)) { int v = q.front(); q.pop(); inq[v] = false; while (excess[v] > 0) { if (next[v] == sz(Base::adj[v])) relabel(v); for (int& i = next[v]; i < sz(Base::adj[v]); ++i) { auto& e = Base::adj[v][i]; if (pi[v] + e.cost - pi[e.to] < 0 && e.rem_cap) { push(e, min(excess[v], e.rem_cap)); if (excess[e.to] > 0 && !inq[e.to]) q.push(e.to), inq[e.to] = true; if (!excess[v]) break; } } } } } TotalCost cost{0}; rep(v, n) trav(e, Base::adj[v]) cost += TotalCost(e.cost / Alpha / n) * TotalCost(e.flow()); return cost / 2; } }; // end "cp-lib/graph/flow/cost-scaling.hpp" // begin "cp-lib/graph/flow/ssp.hpp" template <class Flow = ll, class Cost = ll> struct SuccessiveShortestPathFlowGraph : cp_lib_flow::FlowGraph<Flow, Cost> { private: using Base = cp_lib_flow::FlowGraph<Flow, Cost>; static constexpr auto mcmf_limiter = [](auto, auto, auto aug, auto) { return aug; }; vector<Cost> bellman_ford() { vector<uint8_t> inq(sz(Base::adj), true); vector<Cost> dist(sz(Base::adj)); queue<int> q; rep(v, sz(Base::adj)) q.push(v); while (sz(q)) { int v = q.front(); q.pop(); inq[v] = false; trav(e, Base::adj[v]) { if (!e.rem_cap || dist[v] + e.cost >= dist[e.to]) continue; dist[e.to] = dist[v] + e.cost; if (!inq[e.to]) inq[e.to] = true, q.push(e.to); } } return dist; } public: using Base::Base; int add_edge(int s, int t, Flow cap, Cost cost) { int idx = sz(Base::adj[s]), idx_rev = (s == t ? idx + 1 : sz(Base::adj[t])); Base::adj[s].push_back(typename Base::Edge{{t, idx_rev, cap, cap}, cost}); Base::adj[t].push_back(typename Base::Edge{{s, idx, Flow(0), Flow(0)}, -cost}); return idx; } template <class F = decltype(mcmf_limiter), class TotalCost = ll> tuple<Flow, TotalCost, vector<Cost>> calc_cost_flow(int s, int t, F limiter = mcmf_limiter, bool negative_edges = true) { int n = sz(Base::adj); auto pi = (negative_edges ? bellman_ford() : vector(n, Cost(0))); vector dist(n, numeric_limits<Cost>::max()); vector<int> seen; vector<typename Base::Edge*> inc(n); Flow flow{0}; TotalCost total_cost{0}; while (true) { priority_queue<pair<Cost, int>> q; q.emplace(Cost(0), s); fill(all(dist), numeric_limits<Cost>::max()); dist[s] = Cost(0); seen.clear(); while (sz(q) && q.top().second != t) { auto [d, v] = q.top(); q.pop(); d = -d; if (d > dist[v]) continue; seen.push_back(v); d += pi[v]; trav(e, Base::adj[v]) { auto new_dist = d + e.cost - pi[e.to]; if (e.rem_cap && new_dist < dist[e.to]) dist[e.to] = new_dist, q.emplace(-new_dist, e.to), inc[e.to] = &e; } } if (!sz(q)) break; auto dt = -q.top().first; trav(v, seen) pi[v] += dist[v] - dt; Flow bottleneck = numeric_limits<Flow>::max(); Cost aug_cost{0}; for (int v = t; v != s; v = Base::adj[inc[v]->to][inc[v]->rev].to) bottleneck = min(bottleneck, inc[v]->rem_cap), aug_cost += inc[v]->cost; auto aug = limiter(flow, total_cost, bottleneck, aug_cost); flow += aug; total_cost += TotalCost(aug) * TotalCost(aug_cost); for (int v = t; v != s; v = Base::adj[inc[v]->to][inc[v]->rev].to) inc[v]->rem_cap -= aug, Base::adj[inc[v]->to][inc[v]->rev].rem_cap += aug; if (aug < bottleneck) break; } return {flow, total_cost, move(pi)}; } }; // end "cp-lib/graph/flow/ssp.hpp" int main() { cin.tie(0)->sync_with_stdio(false); int n; cin >> n; vector e(n, vector(n, 0)); int s = 2 * n, t = s + 1; // SuccessiveShortestPathFlowGraph<int, ll> g(2 * n + 2); // CostScalingFlowGraph<int, ll> g(2 * n + 2); CapacityScalingFlowGraph<int, ll> g(2 * n + 2); rep(i, n) rep(j, n) { int c; cin >> c; e[i][j] = g.add_edge(i, j + n, 1, c); } rep(i, n) g.add_edge(s, i, 1, 0), g.add_edge(i + n, t, 1, 0); vector supply(2 * n + 2, 0); supply[s] = n; supply[t] = -n; // auto [_1, cost, _2] = g.calc_cost_flow(s, t); // auto cost = g.minimize_circulation(move(supply)); auto [cost, _] = *g.minimize_circulation(move(supply)); cout << cost << '\n'; rep(i, n) rep(j, n) if (g.adj[i][e[i][j]].flow()) cout << j << ' '; cout << '\n'; }