結果
問題 | No.2713 Just Solitaire |
ユーザー | wanui |
提出日時 | 2024-03-31 15:05:51 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 6,478 bytes |
コンパイル時間 | 2,548 ms |
コンパイル使用メモリ | 226,948 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-30 20:14:38 |
合計ジャッジ時間 | 3,661 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 1 ms
6,820 KB |
testcase_04 | AC | 2 ms
6,820 KB |
testcase_05 | AC | 2 ms
6,820 KB |
testcase_06 | AC | 2 ms
6,820 KB |
testcase_07 | AC | 1 ms
6,816 KB |
testcase_08 | AC | 2 ms
6,816 KB |
testcase_09 | AC | 2 ms
6,816 KB |
testcase_10 | AC | 2 ms
6,816 KB |
testcase_11 | AC | 2 ms
6,816 KB |
testcase_12 | AC | 2 ms
6,820 KB |
testcase_13 | AC | 2 ms
6,820 KB |
testcase_14 | AC | 2 ms
6,816 KB |
testcase_15 | AC | 2 ms
6,820 KB |
testcase_16 | AC | 2 ms
6,820 KB |
testcase_17 | AC | 2 ms
6,820 KB |
testcase_18 | AC | 2 ms
6,820 KB |
testcase_19 | AC | 2 ms
6,820 KB |
testcase_20 | AC | 1 ms
6,816 KB |
testcase_21 | AC | 1 ms
6,816 KB |
testcase_22 | AC | 1 ms
6,816 KB |
testcase_23 | AC | 2 ms
6,820 KB |
testcase_24 | AC | 3 ms
6,816 KB |
testcase_25 | AC | 3 ms
6,816 KB |
testcase_26 | AC | 3 ms
6,820 KB |
testcase_27 | AC | 3 ms
6,816 KB |
testcase_28 | AC | 3 ms
6,816 KB |
testcase_29 | AC | 3 ms
6,820 KB |
testcase_30 | AC | 3 ms
6,816 KB |
testcase_31 | AC | 3 ms
6,820 KB |
testcase_32 | AC | 3 ms
6,816 KB |
testcase_33 | AC | 3 ms
6,816 KB |
ソースコード
#include <bits/stdc++.h> // clang-format off using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair<ll,ll>; const ll INF=4e18; void print0(){}; template<typename H,typename... T> void print0(H h,T... t){cout<<h;print0(t...);} void print1(){print0("\n");}; template<typename H,typename... T>void print1(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print1(t...);} void ioinit() { cout<<fixed<<setprecision(15); cerr<<fixed<<setprecision(6); ios_base::sync_with_stdio(0); cin.tie(0); } #define debug1(a) { cerr<<#a<<":"<<a<<endl; } #define debug2(a,b) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<endl; } #define debug3(a,b,c) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<endl; } #define debug4(a,b,c,d) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<" "<<#d<<":"<<d<<endl; } // clang-format on using CAP = ll; const CAP CAP_INF = 1e18; struct flowedg { int id; int v; CAP cap; CAP orgcap; int rev; }; class flow_dinic { public: vector<vector<int>> edgmap; vector<flowedg> edgs; vector<int> route; vector<int> level; vector<int> searched_edge; int V; flow_dinic(int nodenum) { V = nodenum; edgmap.resize(V + 1); } void addedge(int u, int v, CAP cap) { int fwd_id = edgs.size(); int rev_id = edgs.size() + 1; edgs.push_back({fwd_id, v, cap, cap, rev_id}); edgs.push_back({rev_id, u, 0, 0, fwd_id}); edgmap[u].push_back(fwd_id); edgmap[v].push_back(rev_id); } CAP maxflow(int start, int goal) { // スタートに向かうダミーエッジを作る int fwd_id = edgs.size(); int rev_id = edgs.size() + 1; edgs.push_back({fwd_id, start, CAP_INF, CAP_INF, rev_id}); edgs.push_back({rev_id, V, 0, 0, fwd_id}); edgmap[V].push_back(fwd_id); edgmap[start].push_back(rev_id); const int level_inf = 1e9; while (true) { level.resize(0); level.resize(V + 1, level_inf); searched_edge.resize(0); searched_edge.resize(V + 1, 0); bfs(V); bool level_ok = false; while (true) { route.resize(0); CAP fmax = dfs(fwd_id, CAP_INF, goal); if (fmax >= 0) { level_ok = true; for (auto eid : route) { edgs[eid].cap -= fmax; edgs[edgs[eid].rev].cap += fmax; } } else { break; } } if (!level_ok) break; } CAP ans = edgs[fwd_id].orgcap - edgs[fwd_id].cap; // ダミーエッジ削除 edgmap[V].pop_back(); edgmap[start].pop_back(); edgs.pop_back(); edgs.pop_back(); return ans; } void bfs(int u0) { // startからの距離をlevelに入れる queue<pair<int, int>> q; q.push({u0, 0}); while (!q.empty()) { pair<int, int> ul = q.front(); q.pop(); int u = ul.first; int lv = ul.second; if (level[u] <= lv) continue; level[u] = lv; for (auto neid : edgmap[u]) { if (edgs[neid].cap > 0) { // capが残っているedgeのみ利用 q.push({edgs[neid].v, lv + 1}); } } } } CAP dfs(int eid, CAP fmax, int goal) { route.push_back(eid); int u = edgs[eid].v; if (u == goal) { return fmax; } // searched_edge[u] -> ノードuについて、searched_edge[u] より小さいedgeは全て探索済みである while (searched_edge[u] < (int)edgmap[u].size()) { int neid = edgmap[u][searched_edge[u]]; int v = edgs[neid].v; if (level[u] < level[v] && edgs[neid].cap > 0) { // capが残っていて、levelが増えるedgeのみ利用 CAP nxt_fmax = min(fmax, edgs[neid].cap); CAP result = dfs(neid, nxt_fmax, goal); if (result >= 0) { return result; } } searched_edge[u]++; } route.pop_back(); return -1; } }; // 燃やす埋める問題とProject Selection Problemの整理 // https://qiita.com/tanaka-a/items/fb8d84c44190c7098047 class project_selection_problem { public: flow_dinic mf; vector<CAP> ps; int start; int goal; project_selection_problem(int nodenum, int start_, int goal_) : mf(nodenum) { ps.resize(nodenum); start = start_; goal = goal_; } void add_profit(int u, CAP p) { // uを実施する場合、利得pを得る (pは負のこともありうる) ps[u] = p; if (p > 0) { mf.addedge(start, u, p); } else { mf.addedge(u, goal, -p); } } void add_rule(int x, int y, CAP z) { // x実施し、かつyを実施しない場合、損失zを得る (z>=0) mf.addedge(x, y, z); } CAP solve() { // 得られる最大の利得を求める CAP ans = 0; for (int i = 0; i < mf.V; i++) { ans += max(CAP(0), ps[i]); } ans -= mf.maxflow(start, goal); return ans; } }; // https://atcoder.jp/contests/abc225/tasks/abc225_g int h, w; int nodeid(int i, int j) { return i * w + j; } int main() { ioinit(); ll N, M; cin >> N >> M; vector<ll> A(N); for (ll i = 0; i < N; i++) { cin >> A[i]; } vector<ll> B(M); for (ll j = 0; j < M; j++) { cin >> B[j]; } vector<vector<bool>> C(M, vector<bool>(N)); for (ll j = 0; j < M; j++) { ll k; cin >> k; for (ll x = 0; x < k; x++) { ll c; cin >> c; c--; C[j][c] = true; } } ll V = N + M + 2; ll start = V - 2; ll goal = V - 1; auto psp = project_selection_problem(V, start, goal); for (ll i = 0; i < N; i++) { psp.add_profit(i, -A[i]); } for (ll j = 0; j < M; j++) { psp.add_profit(j + N, B[j]); } for (ll i = 0; i < N; i++) { for (ll j = 0; j < M; j++) { if (C[j][i]) { psp.add_rule(j + N, i, CAP_INF); } } } print1(psp.solve()); }