結果

問題 No.2713 Just Solitaire
コンテスト
ユーザー KKT89
提出日時 2024-03-31 14:24:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 3,246 bytes
コンパイル時間 3,179 ms
コンパイル使用メモリ 229,228 KB
最終ジャッジ日時 2025-02-20 17:13:01
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }

template<typename T>
struct dinic{
    struct edge{
        int to;
        T c,f;
    };
    T eps;
    const T inf=numeric_limits<T>::max();
    int n,m = 0;
    vector<edge> e;
    vector<vector<int>> g;
    vector<int> level, ptr;
    dinic(int n): n(n), g(n), level(n), ptr(n) {
        eps = (T)1 / (T)1e9;
    }
    void add_edge(int s, int t, T c){
        e.push_back({t, c, 0});
        e.push_back({s, 0, 0});
        g[s].push_back(m++);
        g[t].push_back(m++);
    }
    bool bfs(int s, int t){
        fill(level.begin(), level.end(), -1);
        level[s] = 0;
        for(queue<int> q({s});q.size();q.pop()){
            int s = q.front();
            for(int i:g[s]){
                int t = e[i].to;
                if(level[t] == -1 and (e[i].c - e[i].f) > eps){
                    level[t] = level[s] + 1;
                    q.push(t);
                }
            }
        }
        return (level[t] != -1);
    }
    T dfs(int s, int t, T psh){
        if(!(psh > eps) or s == t) return psh;
        for(int &i = ptr[s]; i < (int)g[s].size(); ++i){
            auto &eg = e[g[s][i]];
            if(level[eg.to] != level[s] + 1 or !(eg.c - eg.f > eps)) continue;
            T f = dfs(eg.to, t, min(psh, eg.c-eg.f));
            if(f > eps){
                eg.f += f;
                e[g[s][i]^1].f -= f;
                return f;
            }
        }
        return 0;
    }
    T max_flow(int s, int t){
        T f = 0;
        while(bfs(s,t)){
            fill(ptr.begin(), ptr.end(), 0);
            while(1){
                T c = dfs(s, t, inf);
                if(c > eps){
                    f += c;
                }
                else{
                    break;
                }
            }
        }
        return f;
    }
    // ABC239-G
    vector<bool> min_cut(int s){
        vector<bool> visited(n);
        queue<int> q; q.push(s);
        while(q.size()){
            int p = q.front(); q.pop();
            visited[p] = true;
            for(auto idx:g[p]){
                auto eg = e[idx];
                if(eg.c - eg.f > eps and !visited[eg.to]){
                    visited[eg.to] = true;
                    q.push(eg.to);
                }
            }
        }
        return visited;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m; cin >> n >> m;
    vector<ll> a(n), b(m);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }
    dinic<ll> g(n+m+2);
    int S = n+m, T = n+m+1;
    ll res = 0;
    for (int i = 0; i < n; ++i) {
        g.add_edge(S, i, a[i]);
    }
    for (int i = 0; i < m; ++i) {
        g.add_edge(i+n, T, b[i]);
        res += b[i];
    }
    for (int i = 0; i < m; ++i) {
        int k; cin >> k;
        for (int j = 0; j < k; ++j) {
            int c; cin >> c;
            c -= 1;
            g.add_edge(c, i+n, 1e18);
        }
    }
    cout << res-g.max_flow(S,T) << endl;
}
0