#943184 (C++14) No.2604 Initial Motion

提出ソース

結果

問題	No.2604 Initial Motion
ユーザー	👑 hos.lyric
提出日時	2024-01-12 21:39:06
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	524 ms / 3,000 ms
コード長	5,975 bytes
コンパイル時間	1,528 ms
コンパイル使用メモリ	130,336 KB
実行使用メモリ	6,676 KB
最終ジャッジ日時	2024-01-12 21:39:20
合計ジャッジ時間	12,574 ms
ジャッジサーバーID （参考情報）	judge14 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	2 ms 6,676 KB
testcase_02	AC	2 ms 6,676 KB
testcase_03	AC	12 ms 6,676 KB
testcase_04	AC	12 ms 6,676 KB
testcase_05	AC	12 ms 6,676 KB
testcase_06	AC	13 ms 6,676 KB
testcase_07	AC	12 ms 6,676 KB
testcase_08	AC	12 ms 6,676 KB
testcase_09	AC	12 ms 6,676 KB
testcase_10	AC	12 ms 6,676 KB
testcase_11	AC	12 ms 6,676 KB
testcase_12	AC	12 ms 6,676 KB
testcase_13	AC	386 ms 6,676 KB
testcase_14	AC	323 ms 6,676 KB
testcase_15	AC	129 ms 6,676 KB
testcase_16	AC	359 ms 6,676 KB
testcase_17	AC	434 ms 6,676 KB
testcase_18	AC	411 ms 6,676 KB
testcase_19	AC	414 ms 6,676 KB
testcase_20	AC	361 ms 6,676 KB
testcase_21	AC	327 ms 6,676 KB
testcase_22	AC	407 ms 6,676 KB
testcase_23	AC	342 ms 6,676 KB
testcase_24	AC	386 ms 6,676 KB
testcase_25	AC	524 ms 6,676 KB
testcase_26	AC	360 ms 6,676 KB
testcase_27	AC	298 ms 6,676 KB
testcase_28	AC	343 ms 6,676 KB
testcase_29	AC	377 ms 6,676 KB
testcase_30	AC	312 ms 6,676 KB
testcase_31	AC	358 ms 6,676 KB
testcase_32	AC	441 ms 6,676 KB
testcase_33	AC	157 ms 6,676 KB
testcase_34	AC	245 ms 6,676 KB
testcase_35	AC	461 ms 6,676 KB
testcase_36	AC	478 ms 6,676 KB
testcase_37	AC	143 ms 6,676 KB
testcase_38	AC	2 ms 6,676 KB
testcase_39	AC	2 ms 6,676 KB
testcase_40	AC	284 ms 6,676 KB
testcase_41	AC	281 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


// Minimum cost flow by successive shortest paths.
// Assumes that there exists no negative-cost cycle.
// TODO: Check the range of intermediate values.
template <class Flow, class Cost> struct MinCostFlow {
  // Watch out when using types other than int and long long.
  static constexpr Flow FLOW_EPS = 1e-10L;
  static constexpr Flow FLOW_INF = std::numeric_limits<Flow>::max();
  static constexpr Cost COST_EPS = 1e-10L;
  static constexpr Cost COST_INF = std::numeric_limits<Cost>::max();

  int n, m;
  vector<int> ptr, nxt, zu;
  vector<Flow> capa;
  vector<Cost> cost;

  explicit MinCostFlow(int n_) : n(n_), m(0), ptr(n_, -1) {}
  void ae(int u, int v, Flow w, Cost c) {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    assert(0 <= w);
    nxt.push_back(ptr[u]); zu.push_back(v); capa.push_back(w); cost.push_back( c); ptr[u] = m++;
    nxt.push_back(ptr[v]); zu.push_back(u); capa.push_back(0); cost.push_back(-c); ptr[v] = m++;
  }

  vector<Cost> pot, dist;
  vector<bool> vis;
  vector<int> pari;

  // cost slopes[j] per flow when flows[j] <= flow <= flows[j + 1]
  vector<Flow> flows;
  vector<Cost> slopes;

  // Finds a shortest path from s to t in the residual graph.
  // O((n + m) log m) time.
  //   Assumes that the members above are set.
  //   The distance to a vertex might not be determined if it is >= dist[t].
  //   You can pass t = -1 to find a shortest path to each vertex.
  void shortest(int s, int t) {
    using Entry = pair<Cost, int>;
    priority_queue<Entry, vector<Entry>, std::greater<Entry>> que;
    for (int u = 0; u < n; ++u) { dist[u] = COST_INF; vis[u] = false; }
    for (que.emplace(dist[s] = 0, s); !que.empty(); ) {
      const Cost c = que.top().first;
      const int u = que.top().second;
      que.pop();
      if (vis[u]) continue;
      vis[u] = true;
      if (u == t) return;
      for (int i = ptr[u]; ~i; i = nxt[i]) if (capa[i] > FLOW_EPS) {
        const int v = zu[i];
        if (!vis[v]) {
          const Cost cc = c + cost[i] + pot[u] - pot[v];
          if (dist[v] > cc) { que.emplace(dist[v] = cc, v); pari[v] = i; }
        }
      }
    }
  }

  // Finds a minimum cost flow from s to t of amount min{(max flow), limFlow}.
  //   Bellman-Ford takes O(n m) time, or O(m) time if there is no negative-cost
  //   edge, or cannot stop if there exists a negative-cost cycle.
  //   min{(max flow), limFlow} shortest paths if Flow is an integral type.
  pair<Flow, Cost> run(int s, int t, Flow limFlow = FLOW_INF) {
    assert(0 <= s); assert(s < n);
    assert(0 <= t); assert(t < n);
    assert(s != t);
    assert(0 <= limFlow);
    pot.assign(n, 0);
    for (; ; ) {
      bool upd = false;
      for (int i = 0; i < m; ++i) if (capa[i] > FLOW_EPS) {
        const int u = zu[i ^ 1], v = zu[i];
        const Cost cc = pot[u] + cost[i];
        if (pot[v] > cc + COST_EPS) { pot[v] = cc; upd = true; }
      }
      if (!upd) break;
    }
    dist.resize(n);
    vis.resize(n);
    pari.resize(n);
    Flow totalFlow = 0;
    Cost totalCost = 0;
    flows.clear(); flows.push_back(0);
    slopes.clear();
    for (; totalFlow < limFlow; ) {
      shortest(s, t);
      if (!vis[t]) break;
      for (int u = 0; u < n; ++u) pot[u] += min(dist[u], dist[t]);
      Flow f = limFlow - totalFlow;
      for (int v = t; v != s; ) {
        const int i = pari[v]; if (f > capa[i]) { f = capa[i]; } v = zu[i ^ 1];
      }
      for (int v = t; v != s; ) {
        const int i = pari[v]; capa[i] -= f; capa[i ^ 1] += f; v = zu[i ^ 1];
      }
      totalFlow += f;
      totalCost += f * (pot[t] - pot[s]);
      flows.push_back(totalFlow);
      slopes.push_back(pot[t] - pot[s]);
    }
    return make_pair(totalFlow, totalCost);
  }
};

////////////////////////////////////////////////////////////////////////////////


int K, N, M;
vector<int> A;
vector<int> B;
vector<int> U, V;
vector<Int> D;

int main() {
  for (; ~scanf("%d%d%d", &K, &N, &M); ) {
    A.resize(K);
    for (int k = 0; k < K; ++k) {
      scanf("%d", &A[k]);
      --A[k];
    }
    B.resize(N);
    for (int u = 0; u < N; ++u) {
      scanf("%d", &B[u]);
    }
    U.resize(M);
    V.resize(M);
    D.resize(M);
    for (int i = 0; i < M; ++i) {
      scanf("%d%d%lld", &U[i], &V[i], &D[i]);
      --U[i];
      --V[i];
    }
    
    MinCostFlow<int, Int> mcf(N + 2);
    const int src = N, snk = N + 1;
    for (int k = 0; k < K; ++k) {
      mcf.ae(src, A[k], 1, 0);
    }
    for (int u = 0; u < N; ++u) {
      mcf.ae(u, snk, B[u], 0);
    }
    for (int i = 0; i < M; ++i) {
      mcf.ae(U[i], V[i], K, D[i]);
      mcf.ae(V[i], U[i], K, D[i]);
    }
    const auto res = mcf.run(src, snk, K);
    assert(res.first == K);
    printf("%lld\n", res.second);
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード