#680479 (C++17) No.1615 Double Down

提出ソース

結果

問題	No.1615 Double Down
ユーザー	ei1333333
提出日時	2021-07-21 22:33:07
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	9,277 bytes
コンパイル時間	2,640 ms
コンパイル使用メモリ	219,152 KB
実行使用メモリ	16,152 KB
最終ジャッジ日時	2024-07-17 19:33:43
合計ジャッジ時間	25,293 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	TLE	-
testcase_01	--	-
testcase_02	--	-
testcase_03	--	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-
testcase_45	--	-
testcase_46	--	-
testcase_47	--	-
testcase_48	--	-
testcase_49	--	-
testcase_50	--	-
testcase_51	--	-
testcase_52	--	-
testcase_53	--	-
testcase_54	--	-
testcase_55	--	-
testcase_56	--	-

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

ソースコード

raw source code

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;
// const int mod = 1e9 + 7;
const int mod = 31607;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}


template< typename CapType, typename TotalCapType, typename CostType, typename TotalCostType >
class CostScaling {
private:
  static const int alpha = 8;  // eps <- max(1, eps / alpha)

  using cap_t = CapType;
  using tcap_t = TotalCapType;
  using cost_t = CostType;  // > max{|C|} * (2 * |V|)
  using tcost_t = TotalCostType;
  static constexpr cost_t Inf = (tcap_t(1) << (sizeof(tcap_t) * 8 - 2)) - 1;

  struct InputEdge {
    int from, to;
    cap_t b, c;
    cost_t cost;
  };
  struct Edge {
    int to, rev;
    cap_t cap;
    cost_t cost;
  };

  class Dinic {
  public:
    Dinic(int N, const vector< int > &ofs, vector< Edge > &edges, vector< tcap_t > &capacity)
        : N(N), ofs(ofs), edges(edges), capacity(capacity), last(N) {}

    bool succeeded() {
      // s -> u: capacity[u]
      // u -> t: capacity[u + N]
      tcap_t f = 0;

      for(int u = 0; u < N; ++u)
        f += capacity[u];

      vector< int > que(N);

      while(f) {
        dist.assign(N, -1);
        int qh = 0, qt = 0, lv = N;

        for(int u = 0; u < N; ++u)
          if(capacity[u] > 0)
            que[qt++] = u, dist[u] = 0;

        for(; qh < qt;) {
          int u = que[qh++];

          if(lv == N && capacity[u + N] > 0)
            lv = dist[u];

          if(dist[u] > lv)
            break;

          for(int ei = ofs[u]; ei < ofs[u + 1]; ++ei) {
            int v = edges[ei].to;

            if(edges[ei].cap > 0 && dist[v] == -1) {
              que[qt++] = v, dist[v] = dist[u] + 1;
            }
          }
        }

        if(lv == N)
          break;

        for(int u = 0; u < N; ++u)
          last[u] = ofs[u];

        for(int u = 0; u < N; ++u)
          if(capacity[u] > 0) {
            auto df = block_flow(u, capacity[u]);
            f -= df, capacity[u] -= df;
          }
      }

      return f == 0;
    }

  private:
    tcap_t block_flow(int u, tcap_t f) {
      tcap_t ret = 0;

      if(capacity[u + N] > 0) {
        tcap_t df = min(f, capacity[u + N]);
        capacity[u + N] -= df;
        return df;
      }

      for(auto &ei = last[u]; ei < ofs[u + 1]; ++ei) {
        auto &e = edges[ei];
        int v = e.to;

        if(e.cap == 0 || dist[v] <= dist[u])
          continue;

        cap_t df = block_flow(v, min< cap_t >(e.cap, f));

        if(df == 0)
          continue;

        e.cap -= df, edges[e.rev].cap += df;
        f -= df, ret += df;

        if(f == 0)
          break;
      }

      return ret;
    }

    int N;
    const vector< int > &ofs;
    vector< Edge > &edges;
    vector< tcap_t > &capacity;
    vector< int > last, dist;
  };

public:
  CostScaling(int N, int M = 0) : N(N), capacity(2 * N) {
    if(M > 0)
      in.reserve(M);
  }

  void add_directed_edge(int u, int v, cap_t b, cap_t c, cost_t cost) {
    if(b > 0)
      capacity[v] += b, capacity[u + N] += b;
    else
      capacity[u] += -b, capacity[v + N] += -b;

    in.push_back({u, v, b, c, cost});
  }

  pair< bool, tcost_t > minimum_cost_circulation() {
    construct();

    if(!has_feasible_circulation())
      return {false, 0};

    const int cost_multiplier = 2 << __lg(N);  // should be > |V|

    cost_t eps = 0;

    for(auto &e : edges)
      e.cost *= cost_multiplier, eps = max(eps, e.cost);

    while(eps > 1)
      refine(eps = max< cost_t >(1, eps / alpha));

    tcost_t ret = initial_cost;

    for(auto &e : edges)
      ret -= (e.cost / cost_multiplier) * e.cap;

    return {true, ret / 2};
  }

private:
  void refine(const cost_t eps) {
    auto cost_p = [&](int u, const Edge &e) {
      return e.cost + potential[u] - potential[e.to];
    };

    for(int u = 0; u < N; ++u)
      for(int i = ofs[u]; i < ofs[u + 1]; ++i) {
        auto &e = edges[i];

        if(cost_p(u, e) < 0)
          edges[e.rev].cap += e.cap, e.cap = 0;
      }

    vector< tcap_t > excess(initial_excess);

    for(auto &e : edges)
      excess[e.to] -= e.cap;

    vector< int > stack;
    stack.reserve(N);

    for(int u = 0; u < N; ++u)
      if(excess[u] > 0)
        stack.push_back(u);

    auto residue = [&](const Edge &e) -> cap_t { return e.cap; };
    auto push = [&](int u, Edge &e, cap_t df) {
      e.cap -= df;
      edges[e.rev].cap += df;
      excess[e.to] += df;
      excess[u] -= df;

      if(excess[e.to] > 0 && excess[e.to] <= df) {
        stack.push_back(e.to);
      }
    };
    auto relabel = [&](int u, cost_t delta) {
      potential[u] -= delta + eps;
    };
    auto relabel_in_advance = [&](int u) {
      if(excess[u] != 0)
        return false;

      auto delta = Inf;

      for(int ei = ofs[u]; ei < ofs[u + 1]; ++ei) {
        auto &e = edges[ei];

        if(residue(e) == 0)
          continue;

        if(cost_p(u, e) < 0)
          return false;
        else
          delta = min< tcost_t >(delta, cost_p(u, e));
      }

      relabel(u, delta);
      return true;
    };
    auto discharge = [&](int u) {
      auto delta = Inf;

      for(int ei = ofs[u]; ei < ofs[u + 1]; ++ei) {
        auto &e = edges[ei];

        if(residue(e) == 0)
          continue;

        if(cost_p(u, e) < 0) {
          if(relabel_in_advance(e.to)) {
            --ei;
            continue;  // modify ei (!)
          }

          cap_t df = min< tcap_t >(excess[u], residue(e));
          push(u, e, df);

          if(!excess[u])
            return;
        } else
          delta = min< tcost_t >(delta, cost_p(u, e));
      }

      relabel(u, delta);
      stack.push_back(u);
    };

    while(!stack.empty()) {
      auto u = stack.back();
      stack.pop_back();
      discharge(u);
    }
  }

  void construct() {
    ofs.assign(N + 1, 0);
    edges.resize(2 * in.size());
    initial_excess.assign(N, 0);
    initial_cost = 0;
    potential.assign(N, 0);

    for(auto &e : in)
      ofs[e.from + 1]++, ofs[e.to + 1]++;

    for(int i = 1; i <= N; ++i)
      ofs[i] += ofs[i - 1];

    for(auto &e : in) {
      initial_excess[e.to] += e.c;
      initial_excess[e.from] += -e.b;
      initial_cost += tcost_t(e.cost) * (e.c + e.b);
      edges[ofs[e.from]++] = {e.to, ofs[e.to], e.c - e.b, e.cost};
      edges[ofs[e.to]++] = {e.from, ofs[e.from] - 1, 0, -e.cost};
    }

    for(int i = N; i > 0; --i)
      ofs[i] = ofs[i - 1];

    ofs[0] = 0;
  }

  bool has_feasible_circulation() {
    return Dinic(N, ofs, edges, capacity).succeeded();
  }

private:
  int N;
  vector< InputEdge > in;
  vector< tcap_t > capacity;

  vector< int > ofs;
  vector< Edge > edges;

  tcost_t initial_cost;
  vector< tcap_t > initial_excess;
  vector< tcost_t > potential;
};
// cap, total_cap, cost * (2 * |V|), total_cost
using MCC = CostScaling< int64_t, int64_t, int64_t, int64_t >;

int main() {
  int N, M, K, L;
  cin >> N >> M >> K >> L;
  MCC flow(N + M + 2, L + N + 2);
  int S = N + M, T = N + M + 1;
  for(int i = 0; i < L; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    --x, --y;
    flow.add_directed_edge(x, y + N, 0, 1, -(1 << z));
  }
  for(int i = 0; i < N; i++) {
    flow.add_directed_edge(S, i, 0, 1, 0);
    flow.add_directed_edge(i, T, 0, 1, 0);
  }
  for(int i = 0; i < M; i++) {
    flow.add_directed_edge(i + N, T, 0, 1, 0);
  }
  flow.add_directed_edge(T, S, N, N, 0);
  cout << -flow.minimum_cost_circulation().second << "\n";
}

yukicoder

結果

テストケース

ソースコード