Submit Info #59701

Problem Lang User Status Time Memory
Assignment Problem cpp Felerius AC 1823 ms 21.19 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.45 MiB
hand_minus_00 AC 415 ms 13.39 MiB
hand_plus_00 AC 1823 ms 21.19 MiB
max_random_00 AC 310 ms 13.39 MiB
max_random_01 AC 310 ms 13.49 MiB
max_random_02 AC 314 ms 13.39 MiB
max_random_03 AC 310 ms 13.41 MiB
max_random_04 AC 307 ms 13.50 MiB
random_00 AC 21 ms 2.77 MiB
random_01 AC 28 ms 3.07 MiB
random_02 AC 4 ms 1.07 MiB
random_03 AC 26 ms 2.95 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/ssp.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> 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); 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); auto [_1, cost, _2] = g.calc_cost_flow(s, t); cout << cost << '\n'; rep(i, n) rep(j, n) if (g.adj[i][e[i][j]].flow()) cout << j << ' '; cout << '\n'; }