結果

問題 No.1678 Coin Trade (Multiple)
ユーザー 👑 Nachia
提出日時 2021-09-10 22:00:30
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,266 ms / 5,000 ms
コード長 2,857 bytes
コンパイル時間 4,150 ms
コンパイル使用メモリ 128,632 KB
最終ジャッジ日時 2025-01-24 10:41:26
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 56
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(n); i++)



#include <vector>
#include <queue>

template<class T>
using nega_queue = priority_queue<T, vector<T>, greater<T>>;

struct MinCostFlow {
    using cap = i64;
    using cost = i64;
    struct Edge { int to, rev; cap c; cost d; };

    int N;
    int src = 0, snk = 1;
    vector<vector<Edge>> E;

    cost fAns = 0;
    vector<cost> D, P;
    vector<int> PE;

    MinCostFlow(int n) {
        N = n;
        E.resize(n);
        D.resize(n);
        PE.resize(n);
        P.resize(n);
    }

    void add_edge(int u, int v, cap c, cost d) {
        E[u].push_back(Edge{ v, (int)E[v].size(), c, d });
        E[v].push_back(Edge{ u, (int)E[u].size() - 1, 0, -d });
    }

    void dijkstra() {
        rep(i, N) D[i] = PE[i] = -1;
        nega_queue<pair<cost, int>> Q;
        Q.push({ 0, src });
        D[src] = 0;
        while (Q.size()) {
            auto d = Q.top().first;
            int p = Q.top().second;
            Q.pop();
            if (D[p] != d) continue;
            for (Edge e : E[p]) if (e.c != 0) {
                auto nxd = d + e.d + P[p] - P[e.to];
                if (D[e.to] != -1 && D[e.to] <= nxd) continue;
                D[e.to] = nxd;
                PE[e.to] = e.rev;
                Q.push({ nxd, e.to });
            }
        }
        rep(i, N) if(D[i] != -1) P[i] += D[i];
    }

    cost flow(cap f) {
        while (f) {
            dijkstra();
            if (D[snk] == -1) { f = 0; fAns = -1; return fAns; }
            int p = snk;
            cap c = f;
            while (p != src) {
                auto& e = E[p][PE[p]];
                c = min(c, E[e.to][e.rev].c);
                p = e.to;
            }
            p = snk;
            if (c == 0) exit(1);
            while (p != src) {
                auto& e = E[p][PE[p]];
                auto& re = E[e.to][e.rev];
                e.c += c;
                re.c -= c;
                fAns += c * re.d;
                p = e.to;
            }
            f -= c;
        }
        return fAns;
    }
};


int main(){
  int N,K; cin >> N >> K;
  vector<i64> A(N);
  vector<vector<int>> E(N);
  rep(i,N){
    int c; cin >> A[i] >> c;
    E[i].resize(c);
    rep(j,c){ cin >> E[i][j]; E[i][j]--; }
  }

  const i64 maxA = 1000000000;

  MinCostFlow G(N+1);

  G.src = 0;
  G.snk = N;
  
  rep(i,N) G.add_edge(i,i+1,K,maxA);
  rep(i,N) for(int e : E[i]){
    G.add_edge(e,i,1,maxA*(i-e)-(A[i]-A[e]));
  }

  i64 ans = G.flow(K);
  ans = maxA * N * K - ans;
  cout << ans << endl;
  return 0;
}




struct ios_do_not_sync {
    ios_do_not_sync() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0