結果
問題 |
No.3306 Life is Easy?
|
ユーザー |
|
提出日時 | 2025-10-08 00:26:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 7,928 bytes |
コンパイル時間 | 4,487 ms |
コンパイル使用メモリ | 265,252 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-10-08 00:26:44 |
合計ジャッジ時間 | 13,873 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 WA * 28 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using ll = long long; #define rep(i, s, t) for (ll i = s; i < (ll)(t); i++) #define all(x) begin(x), end(x) template <class T> bool chmin(T& x, T y) { return x > y ? (x = y, true) : false; } template <class T> bool chmax(T& x, T y) { return x < y ? (x = y, true) : false; } struct io_setup { io_setup() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); } } io_setup; using mint = atcoder::modint998244353; // https://github.com/drken1215/algorithm/blob/master/GraphNetworkFlow/min_cost_b_flow_by_network_simplex_method.cpp // Network Simplex Method template <class FLOW, class COST> struct NetworkSimplex { struct Edge { int from, to; FLOW cap; COST cost; friend ostream& operator<<(ostream& s, const Edge& e) { return s << e.from << " -> " << e.to << " (" << e.cap << ", " << e.cost << ")"; } }; struct Parent { int p, e; FLOW up, down; }; // inner values int N, M; vector<Edge> edges; vector<FLOW> lowers; // for edge i vector<FLOW> dss; // for node v (demand and supply) // intermediate results int BUCKET_SIZE, MINOR_LIMIT; vector<Parent> parents; vector<int> depth, nex, pre, candidates; // results bool feasible; COST total_cost; vector<FLOW> flows; vector<COST> pots; // constructor explicit NetworkSimplex(int n = 0) : N(n), dss(n) { } // debugger friend ostream& operator<<(ostream& s, const NetworkSimplex& ns) { s << "feasibility: " << (ns.feasible ? "true" : "false") << '\n'; s << "optimal value: " << ns.total_cost << '\n'; for (int i = 0; i < ns.M; i += 2) { auto e = ns.edges[i]; s << e.from << " -> " << e.to << ": " << ns.flows[i / 2] << " (remained cap: " << e.cap << ", cost: " << e.cost << ")\n"; } for (int v = 0; v < ns.N; v++) cout << "node " << v << ": " << ns.pots[v] << '\n'; return s; } // setter void add_edge(int from, int to, FLOW lower, FLOW upper, COST cost) { edges.push_back({from, to, upper - lower, cost}); edges.push_back({to, from, 0, -cost}); lowers.push_back(lower); dss[from] -= lower; dss[to] += lower; M = (int)edges.size(); } void add_ds(int v, FLOW ds) { assert(v >= 0 && v < N); dss[v] += ds; } // solver pair<bool, COST> solve() { BUCKET_SIZE = max(int(sqrt(double(M)) * 0.2), 10); MINOR_LIMIT = max(int(BUCKET_SIZE * 0.1), 3); precompute(); candidates.reserve(BUCKET_SIZE); int ei = 0; while (true) { for (int i = 0; i < MINOR_LIMIT; i++) if (!minor()) break; COST best = 0; int best_ei = -1; candidates.clear(); for (int i = 0; i < (int)edges.size(); i++) { if (edges[ei].cap) { COST clen = edges[ei].cost + pots[edges[ei ^ 1].to] - pots[edges[ei].to]; if (clen < 0) { if (clen < best) best = clen, best_ei = ei; candidates.push_back(ei); if ((int)candidates.size() == BUCKET_SIZE) break; } } ei++; if (ei == (int)edges.size()) ei = 0; } if (candidates.empty()) break; push_flow(best_ei); } if (!postcompute()) return {false, COST(-1)}; else return {true, total_cost}; } void connect(int a, int b) { nex[a] = b, pre[b] = a; } void precompute() { pots.assign(N + 1, 0); parents.resize(N), depth.assign(N + 1, 1); nex.assign((N + 1) * 2, 0), pre.assign((N + 1) * 2, 0); COST inf_cost = 1; for (int i = 0; i < M; i += 2) { inf_cost += (edges[i].cost >= 0 ? edges[i].cost : -edges[i].cost); } edges.reserve(M + N * 2); for (int i = 0; i < N; i++) { if (dss[i] >= 0) { edges.push_back({i, N, 0, inf_cost}); edges.push_back({N, i, dss[i], -inf_cost}); pots[i] = -inf_cost; } else { edges.push_back({i, N, -dss[i], -inf_cost}); edges.push_back({N, i, 0, inf_cost}); pots[i] = inf_cost; } int e = (int)edges.size() - 2; parents[i] = {N, e, edges[e].cap, edges[e ^ 1].cap}; } depth[N] = 0; for (int i = 0; i < N + 1; i++) connect(i * 2, i * 2 + 1); for (int i = 0; i < N; i++) connect(i * 2 + 1, nex[N * 2]), connect(N * 2, i * 2); } bool postcompute() { for (int i = 0; i < N; i++) { edges[parents[i].e].cap = parents[i].up; edges[parents[i].e ^ 1].cap = parents[i].down; } feasible = true; for (int i = 0; i < N; i++) { if (dss[i] >= 0) { if (edges[M + i * 2 + 1].cap) feasible = false; } else { if (edges[M + i * 2].cap) feasible = false; } } if (!feasible) return false; total_cost = 0; flows.clear(); for (int i = 0; i < M; i += 2) { flows.push_back(lowers[i / 2] + edges[i ^ 1].cap); total_cost += flows.back() * edges[i].cost; } pots.pop_back(); return true; } void push_flow(int ei0) { int u0 = edges[ei0 ^ 1].to, v0 = edges[ei0].to, del_u = v0; FLOW flow = edges[ei0].cap; COST clen = edges[ei0].cost + pots[u0] - pots[v0]; bool del_u_side = true; int lca = get_lca(u0, v0, flow, del_u_side, del_u); if (flow) { int u = u0, v = v0; while (u != lca) parents[u].up += flow, parents[u].down -= flow, u = parents[u].p; while (v != lca) parents[v].up -= flow, parents[v].down += flow, v = parents[v].p; } int u = u0, par = v0; auto p_caps = make_pair(edges[ei0].cap - flow, edges[ei0 ^ 1].cap + flow); COST p_diff = -clen; if (!del_u_side) { swap(u, par); swap(p_caps.first, p_caps.second); p_diff *= -1; } int par_e = ei0 ^ (del_u_side ? 0 : 1); while (par != del_u) { int d = depth[par], idx = u * 2; while (idx != u * 2 + 1) { if (idx % 2 == 0) d++, pots[idx / 2] += p_diff, depth[idx / 2] = d; else d--; idx = nex[idx]; } connect(pre[u * 2], nex[u * 2 + 1]); connect(u * 2 + 1, nex[par * 2]); connect(par * 2, u * 2); swap(parents[u].e, par_e); par_e ^= 1; swap(parents[u].up, p_caps.first); swap(parents[u].down, p_caps.second); swap(p_caps.first, p_caps.second); int next_u = parents[u].p; parents[u].p = par; par = u; u = next_u; } edges[par_e].cap = p_caps.first; edges[par_e ^ 1].cap = p_caps.second; } bool minor() { if (candidates.empty()) return false; COST best = 0; int best_ei = -1; int i = 0; while (i < int(candidates.size())) { int ei = candidates[i]; if (!edges[ei].cap) { swap(candidates[i], candidates.back()); candidates.pop_back(); continue; } COST clen = edges[ei].cost + pots[edges[ei ^ 1].to] - pots[edges[ei].to]; if (clen >= 0) { swap(candidates[i], candidates.back()); candidates.pop_back(); continue; } if (clen < best) best = clen, best_ei = ei; i++; } if (best_ei == -1) return false; push_flow(best_ei); return true; } int get_lca(int u, int v, FLOW& flow, bool& del_u_side, int& del_u) { auto up_u = [&]() { if (parents[u].down < flow) flow = parents[u].down, del_u = u, del_u_side = true; u = parents[u].p; }; auto up_v = [&]() { if (parents[v].up <= flow) flow = parents[v].up, del_u = v, del_u_side = false; v = parents[v].p; }; if (depth[u] >= depth[v]) { int num = depth[u] - depth[v]; for (int i = 0; i < num; i++) up_u(); } else { int num = depth[v] - depth[u]; for (int i = 0; i < num; i++) up_v(); } while (u != v) up_u(), up_v(); return u; } }; void solve() { int n, m; cin >> n >> m; NetworkSimplex<ll, ll> g(n * m + n + 1); int st = n * m + n; vector<vector<int>> a(m, vector<int>(n)); rep(i, 0, n) rep(j, 0, m) cin >> a[j][i]; rep(i, 0, n / 2) { g.add_edge(st, n * m + i, 0, 1, 0); } rep(i, n / 2, n) { g.add_edge(n * m + i, st, 0, 1, 0); } rep(i, 0, m) { rep(j, 0, n - 1) { g.add_edge(i * n + j, i * n + j + 1, 0, n, a[i][j] - a[i][j + 1]); } rep(j, 0, n) { g.add_edge(n * m + j, i * n + j, 0, 1, 0); g.add_edge(i * n + j, n * m + j, 0, 1, 0); } } auto [f, res] = g.solve(); assert(f); cout << -res << '\n'; } int main() { int t = 1; // cin >> t; while (t--) solve(); }