結果

問題 No.1678 Coin Trade (Multiple)
ユーザー 👑 NachiaNachia
提出日時 2021-09-10 22:00:30
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 911 ms / 5,000 ms
コード長 2,857 bytes
コンパイル時間 1,008 ms
コンパイル使用メモリ 95,592 KB
実行使用メモリ 16,828 KB
最終ジャッジ日時 2024-06-12 00:03:21
合計ジャッジ時間 15,527 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 80 ms
10,952 KB
testcase_04 AC 439 ms
14,260 KB
testcase_05 AC 170 ms
16,312 KB
testcase_06 AC 129 ms
15,288 KB
testcase_07 AC 418 ms
11,788 KB
testcase_08 AC 265 ms
12,352 KB
testcase_09 AC 184 ms
16,356 KB
testcase_10 AC 97 ms
7,632 KB
testcase_11 AC 318 ms
13,876 KB
testcase_12 AC 91 ms
7,320 KB
testcase_13 AC 683 ms
15,740 KB
testcase_14 AC 231 ms
10,860 KB
testcase_15 AC 239 ms
13,516 KB
testcase_16 AC 53 ms
13,516 KB
testcase_17 AC 193 ms
16,432 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 1 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 2 ms
5,376 KB
testcase_32 AC 1 ms
5,376 KB
testcase_33 AC 2 ms
5,376 KB
testcase_34 AC 2 ms
5,376 KB
testcase_35 AC 1 ms
5,376 KB
testcase_36 AC 2 ms
5,376 KB
testcase_37 AC 2 ms
5,376 KB
testcase_38 AC 2 ms
5,376 KB
testcase_39 AC 2 ms
5,376 KB
testcase_40 AC 2 ms
5,376 KB
testcase_41 AC 2 ms
5,376 KB
testcase_42 AC 2 ms
5,376 KB
testcase_43 AC 2 ms
5,376 KB
testcase_44 AC 2 ms
5,376 KB
testcase_45 AC 2 ms
5,376 KB
testcase_46 AC 2 ms
5,376 KB
testcase_47 AC 2 ms
5,376 KB
testcase_48 AC 879 ms
16,820 KB
testcase_49 AC 879 ms
16,828 KB
testcase_50 AC 879 ms
16,688 KB
testcase_51 AC 895 ms
16,684 KB
testcase_52 AC 885 ms
16,688 KB
testcase_53 AC 911 ms
16,812 KB
testcase_54 AC 866 ms
16,820 KB
testcase_55 AC 881 ms
16,820 KB
testcase_56 AC 883 ms
16,688 KB
testcase_57 AC 888 ms
16,680 KB
testcase_58 AC 384 ms
15,020 KB
権限があれば一括ダウンロードができます

ソースコード

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