結果
| 問題 |
No.2713 Just Solitaire
|
| コンテスト | |
| ユーザー |
 wanui
|
| 提出日時 | 2024-03-31 15:05:51 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 2,000 ms |
| コード長 | 6,478 bytes |
| コンパイル時間 | 2,592 ms |
| コンパイル使用メモリ | 217,976 KB |
| 最終ジャッジ日時 | 2025-02-20 17:36:28 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 32 |
ソースコード
#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());
}