結果

問題 No.1984 [Cherry 4th Tune *] Dilemma
コンテスト
ユーザー 🍮かんプリン
提出日時 2022-06-21 01:26:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 7,274 bytes
コンパイル時間 2,667 ms
コンパイル使用メモリ 200,356 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-08 14:08:53
合計ジャッジ時間 8,278 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 68
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2022.06.21 01:26:34
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;


struct Dinic {
private:
    struct edge {
        int to;
        ll cap;
        int rev;
        bool isrev;
        int idx;
    };

    vector< vector< edge > > graph;
    vector< int > min_cost, iter;

    bool bfs(int s, int t) {
        min_cost.assign(graph.size(), -1);
        queue< int > que;
        min_cost[s] = 0;
        que.push(s);
        while (!que.empty() && min_cost[t] == -1) {
            int p = que.front();
            que.pop();
            for (auto &e : graph[p]) {
                if (e.cap == 0 || min_cost[e.to] != -1) continue;
                min_cost[e.to] = min_cost[p] + 1;
                que.push(e.to);
            }
        }
        return min_cost[t] != -1;
    }

    ll dfs(const int s, int v, ll flow) {
        if (v == s) return flow;
        ll res = 0;
        int min_cost_v = min_cost[v];
        for (int &i = iter[v]; i < (int)graph[v].size(); i++) {
            edge &e = graph[v][i];
            if (graph[e.to][e.rev].cap == 0 || min_cost_v <= min_cost[e.to]) continue;
            ll d = dfs(s, e.to, min(flow-res, graph[e.to][e.rev].cap));
            if (d <= 0) continue;
            e.cap += d;
            graph[e.to][e.rev].cap -= d;
            res += d;
            if (res == flow) return res;
        }
        min_cost[v] = (int)graph.size();
        return res;
    }
public:

    Dinic() {}
    Dinic(int V) : graph(V) {}

    void add_edge(int from, int to, ll cap, int idx = -1) {
        graph[from].push_back({to, cap, (int)graph[to].size(), false, idx});
        graph[to].push_back({from, 0, (int)graph[from].size() - 1, true, idx});
    }

    ll max_flow(int s, int t, ll flow_limit = 1e18 + 6) {
        ll flow = 0;
        while (bfs(s, t)) {
            if (min_cost[t] == -1) break;
            iter.assign(graph.size(), 0);
            ll f = dfs(s, t, flow_limit-flow);
            if (!f) break;
            flow += f;
        }
        return flow;
    }

    vector<int> min_cnt(int s,int t) {
        vector<bool> visited(graph.size());
        vector<int> ret;
        stack<int> sta;
        visited[s] = true;
        sta.push(s); ret.push_back(s);
        while(!sta.empty()) {
            int v = sta.top(); sta.pop();
            for (auto &e : graph[v]) {
                if (visited[e.to] || e.cap == 0) continue;
                visited[e.to] = true;
                sta.push(e.to);
                ret.push_back(e.to);
            }
        }
        return ret;
    }

    void output() {
        for (int i = 0; i < graph.size(); i++) {
            for (auto &e : graph[i]) {
                if (e.isrev) continue;
                auto &rev_e = graph[e.to][e.rev];
                cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl;
            }
        }
    }
};

struct ProjectSelectionProblem {
    const long long INF = 1e18+1; 
    int n; 
    vector<int> k; 
    vector<int> s; 
    vector<vector<long long>> cost;
    Dinic G;
    long long ans;
    
    ProjectSelectionProblem(vector<int> k) : k(k) {
        n = k.size();
        s = vector<int>(n+1);
        s[0] = 0;
        for (int i = 0; i < n; i++) {
            assert(k[i] >= 2);
            s[i+1] = s[i]+k[i]-1;
        }
        cost = vector<vector<long long>>(n);
        for (int i = 0; i < n; i++) cost[i] = vector<long long>(k[i],0);
        G = Dinic(s[n]+2);
        ans = 0;
    }

    void add_cost_1(int a,vector<long long> x) {
        assert(0 <= a && a < n);
        assert(k[a] == (int)x.size());
        for (int i = 0; i < k[a]; i++) {
            cost[a][i] += x[i];
        }
    }

    void add_cost_2(int a,int b,vector<vector<long long>> x) {
        assert(0 <= a && a < n && 0 <= b && b < n);
        assert((int)x.size() == k[a]);
        for (int i = 0; i < k[a]; i++) {
            assert((int)x[i].size() == k[b]);
            cost[a][i] += x[i][0];
            for (int j = k[b]-1; j >= 0; j--) x[i][j] -= x[i][0];
        }
        for (int i = 1; i < k[b]; i++){
            cost[b][i] += x[k[a]-1][i];
            for (int j = 0; j < k[a]; j++) x[j][i] -= x[k[a]-1][i];
        }
        for (int i = 0; i < k[a]-1; i++){
            for (int j = 0; j < k[b]-1; j++){
                long long c = x[i+1][j]+x[i][j+1]-x[i][j]-x[i+1][j+1];
                assert(c >= 0);
                if (c == 0) continue;
                G.add_edge(s[b]+j, s[a]+i, c);
            }
        }
    }

    long long mincost() {
        for (int i = 0; i < n; i++){
            for (int j = 0; j < k[i]-2; j++) G.add_edge(s[i]+j+1, s[i]+j, INF);
            ans += cost[i][k[i]-1];
            for (int j = 0; j < k[i]-1; j++){
                if (cost[i][j] > cost[i][j+1]) {
                    G.add_edge(s[n], s[i]+j, cost[i][j]-cost[i][j+1]);
                }
                else {
                    G.add_edge(s[i]+j, s[n]+1, cost[i][j+1]-cost[i][j]);
                    ans -= cost[i][j+1]-cost[i][j];
                }
            }
        }
        return ans+G.max_flow(s[n], s[n]+1);
    }

    vector<int> answer() {
        vector<int> ans(n);
        auto v = G.min_cnt(s[n],s[n]+1);
        vector<bool> scut(s[n]+2);
        for (int i = 0; i < v.size(); i++) scut[v[i]] = true;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k[i]-1; j++) {
                if (!scut[s[i]+j]) { ans[i] = j; break; }
                else if (j == k[i]-2) { ans[i] = k[i]-1; }
            }
        }
        return ans;
    }
};

int main() {
    int n,m,k,p;cin >> n >> m >> k >> p;
    ProjectSelectionProblem psp(vector<int>(n+m+k,2));
    vector<int> ();
    for (int i = 0; i < n; i++) {
        vector<ll> cost1(2);
        cin >> cost1[0];
        cost1[0] *= -1;
        psp.add_cost_1(i,cost1);
    }
    for (int i = 0; i < m; i++) {
        vector<ll> cost1(2);
        cin >> cost1[1];
        cost1[1] *= -1;
        psp.add_cost_1(i+n,cost1);
    }
    for (int i = 0; i < k; i++) {
        vector<ll> cost1(2);
        cin >> cost1[0];
        psp.add_cost_1(i+n+m,cost1);
    }
    for (int i = 0; i < n; i++) {
        int L;cin >> L;
        for (int j = 0; j < L; j++) {
            int a;cin >> a;
            vector<vector<ll>> cost2(2,vector<ll>(2));
            cost2[0][1] = 1e10;
            psp.add_cost_2(i,a-1+n+m,cost2);
        }
    }
    for (int i = 0; i < p; i++) {
        int x,y;cin >> x >> y;
        x = x-1;
        y = n+y-1;
        vector<vector<ll>> cost2(2,vector<ll>(2));
        cost2[0][1] = 1e10;
        psp.add_cost_2(x,y,cost2);
    }
    cout << -psp.mincost() << endl;
    auto ans = psp.answer();
    vector<pair<string,int>> ans2;
    for (int i = 0; i < k; i++) {
        if (ans[n+m+i] == 0) ans2.push_back({"Preparation",i+1});
    }
    for (int i = 0; i < n; i++) {
        if (ans[i] == 0) ans2.push_back({"Goal",i+1});
    }
    for (int i = 0; i < m; i++) {
        if (ans[n+i] == 1) ans2.push_back({"Action",i+1});
    }
    cout << ans2.size() << endl;
    for (int i = 0; i < ans2.size(); i++) {
        cout << ans2[i].first << " " << ans2[i].second << endl;
    }
    return 0;
}
0