#604988 (C++17) No.1341 真ん中を入れ替えて門松列

• 問題: No.1341 真ん中を入れ替えて門松列
• ユーザー: 👑 tatyam
• 提出日時: 2021-01-16 03:38:57
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 9,270 bytes
• コンパイル時間: 2,792 ms
• コンパイル使用メモリ: 223,844 KB
• 最終ジャッジ日時: 2025-01-17 21:12:26
• ジャッジサーバーID （参考情報）: judge4 / judge4

ファイルパターン	結果
sample	AC * 5
other	AC * 4 TLE * 10

ソースコード

#include <bits/stdc++.h>
using namespace std;


enum Objective {
    MINIMIZE = 1,
    MAXIMIZE = -1,
};
enum class Status {
    OPTIMAL,
    INFEASIBLE,
};

template <class Flow, class Cost, Objective objective = Objective::MINIMIZE, Flow SCALING_FACTOR = 2>
class MinCostFlow {
  using V_id = uint32_t;
  using E_id = uint32_t;

  class Edge {
    friend class MinCostFlow;

    V_id src, dst;
    Flow flow, cap;
    Cost cost;
    E_id rev;

  public:
    Edge() = default;

    Edge(const V_id src, const V_id dst, const Flow cap, const Cost cost,
         const E_id rev)
        : src(src), dst(dst), flow(0), cap(cap), cost(cost), rev(rev) {}

    [[nodiscard]] Flow residual_cap() const { return cap - flow; }
  };

public:

  class EdgePtr {
    friend class MinCostFlow;

    const MinCostFlow *instance;
    const V_id v;
    const E_id e;

    EdgePtr(const MinCostFlow *instance, const V_id v, const E_id e)
        : instance(instance), v(v), e(e) {}

    [[nodiscard]] const Edge &edge() const { return instance->g[v][e]; }

    [[nodiscard]] const Edge &rev() const {
      const Edge &e = edge();
      return instance->g[e.dst][e.rev];
    }

  public:
    [[nodiscard]] V_id src() const { return rev().dst; }

    [[nodiscard]] V_id dst() const { return edge().dst; }

    [[nodiscard]] Flow flow() const { return edge().flow; }

    [[nodiscard]] Flow lower() const { return -rev().cap; }

    [[nodiscard]] Flow upper() const { return edge().cap; }

    [[nodiscard]] Cost cost() const { return edge().cost; }

    [[nodiscard]] Cost gain() const { return -edge().cost; }
  };

private:
  V_id n;
  std::vector<std::vector<Edge>> g;
  std::vector<Flow> b;

public:
  MinCostFlow() : n(0) {}

  V_id add_vertex() {
    ++n;
    g.resize(n);
    b.resize(n);
    return n-1;
  }

  std::vector<V_id> add_vertices(const size_t size) {
    std::vector<V_id> ret;
    for (V_id i = 0; i < size; ++i) ret.emplace_back(n + i);
    n += size;
    g.resize(n);
    b.resize(n);
    return ret;
  }

  EdgePtr add_edge(const V_id src, const V_id dst, const Flow lower,
                   const Flow upper, const Cost cost) {
    const E_id e = g[src].size(), re = src == dst ? e + 1 : g[dst].size();
    assert(lower <= upper);
    g[src].emplace_back(Edge{src, dst, upper, cost * objective, re});
    g[dst].emplace_back(Edge{dst, src, -lower, -cost * objective, e});
    return EdgePtr{this, src, e};
  }

  void add_supply(const V_id v, const Flow amount) { b[v] += amount; }

  void add_demand(const V_id v, const Flow amount) { b[v] -= amount; }

private:
  // Variables used in calculation
  static Cost constexpr unreachable = std::numeric_limits<Cost>::max();
  Cost farthest;
  std::vector<Cost> potential;
  std::vector<Cost> dist;
  std::vector<Edge *> parent; // out-forrest.
  std::priority_queue<std::pair<Cost, int>, std::vector<std::pair<Cost, int>>,
                      std::greater<>>
      pq; // should be empty outside of dual()
  std::vector<V_id> excess_vs, deficit_vs;

  Edge &rev(const Edge &e) { return g[e.dst][e.rev]; }

  void push(Edge &e, const Flow amount) {
    e.flow += amount;
    g[e.dst][e.rev].flow -= amount;
  }

  Cost residual_cost(const V_id src, const V_id dst, const Edge &e) {
    return e.cost + potential[src] - potential[dst];
  }

  bool dual(const Flow delta) {
    dist.assign(n, unreachable);
    parent.assign(n, nullptr);
    excess_vs.erase(std::remove_if(std::begin(excess_vs), std::end(excess_vs),
                                   [&](const V_id v) { return b[v] < delta; }),
                    std::end(excess_vs));
    deficit_vs.erase(std::remove_if(std::begin(deficit_vs),
                                    std::end(deficit_vs),
                                    [&](const V_id v) { return b[v] > -delta; }),
                     std::end(deficit_vs));
    for (const auto v : excess_vs) pq.emplace(dist[v] = 0, v);
    farthest = 0;
    std::size_t deficit_count = 0;
    while (!pq.empty()) {
      const auto [d, u] = pq.top();
      pq.pop();
      if (dist[u] < d) continue;
      farthest = d;
      if (b[u] <= -delta) ++deficit_count;
      if (deficit_count >= deficit_vs.size()) break;
      for (auto &e : g[u]) {
        if (e.residual_cap() < delta) continue;
        const auto v = e.dst;
        const auto new_dist = d + residual_cost(u, v, e);
        if (new_dist >= dist[v]) continue;
        pq.emplace(dist[v] = new_dist, v);
        parent[v] = &e;
      }
    }
    pq = decltype(pq)(); // pq.clear() doesn't exist.
    for (V_id v = 0; v < n; ++v) {
      potential[v] += std::min(dist[v], farthest);
    }
    return deficit_count > 0;
  }

  void primal(const Flow delta) {
    for (const auto t : deficit_vs) {
      if (dist[t] > farthest) continue;
      Flow f = -b[t];
      V_id v;
      for (v = t; parent[v] != nullptr && f >= delta; v = parent[v]->src) {
        f = std::min(f, parent[v]->residual_cap());
      }
      f = std::min(f, b[v]);
      if (f < delta) continue;
      for (v = t; parent[v] != nullptr;) {
        auto &e = *parent[v];
        push(e, f);
        const size_t u = parent[v]->src;
        parent[v] = nullptr;
        v = u;
      }
      b[t] += f;
      b[v] -= f;
    }
  }

  void saturate_negative(const Flow delta) {
    excess_vs.clear();
    deficit_vs.clear();
    for (auto &es : g) for (auto &e : es) {
      const Flow rcap = e.residual_cap();
      const Cost rcost = residual_cost(e.src, e.dst, e);
      if (rcost < 0 && rcap >= delta) {
        push(e, rcap);
        b[e.src] -= rcap;
        b[e.dst] += rcap;
      }
    }
    for (V_id v = 0; v < n; ++v) if (b[v] != 0) {
      (b[v] > 0 ? excess_vs : deficit_vs).emplace_back(v);
    }
  }

public:
  std::pair<Status, Cost> solve() {
    potential.resize(n);
    for (auto &es : g) for (auto &e : es) {
      const Flow rcap = e.residual_cap();
      if (rcap < 0) {
        push(e, rcap);
        b[e.src] -= rcap;
        b[e.dst] += rcap;
      }
    }

    Flow inf_flow = 1;
    for (const auto &es : g) for (const auto &e : es) inf_flow = std::max(inf_flow, e.residual_cap());
    Flow delta = 1;
    while (delta <= inf_flow) delta *= SCALING_FACTOR;

    for (delta /= SCALING_FACTOR; delta; delta /= SCALING_FACTOR) {
      saturate_negative(delta);
      while (dual(delta)) primal(delta);
    }

    Cost value = 0;
    for (const auto &es : g) for (const auto &e : es) {
      value += e.flow * e.cost;
    }
    value /= 2;

    if (excess_vs.empty() && deficit_vs.empty()) {
      return { Status::OPTIMAL, value / objective };
    } else {
      return { Status::INFEASIBLE, value / objective };
    }
  }

  template<class T>
  T get_result_value() {
    T value = 0;
    for (const auto &es : g) for (const auto &e : es) {
      value += (T)(e.flow) * (T)(e.cost);
    }
    value /= (T)2;
    return value / objective;
  }

  std::vector<Cost> get_potential() {
    // Not strictly necessary, but re-calculate potential to bound the potential values,
    // plus make them somewhat canonical so that it is robust for the algorithm chaneges.
    std::fill(std::begin(potential), std::end(potential), 0);
    for (size_t i = 0; i < n; ++i) for (const auto &es : g) for (const auto &e : es)
      if (e.residual_cap() > 0) potential[e.dst] = std::min(potential[e.dst], potential[e.src] + e.cost);
    return potential;
  }

  std::vector<size_t> get_cut() {
    std::vector<size_t> res;
    if (excess_vs.empty()) return res;
    for (size_t v = 0; v < n; ++v) {
      if (deficit_vs.empty() || (dist[v] < unreachable))
        res.emplace_back(v);
    }
    return res;
  }
};
using ll = int64_t;
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N), B(N), C(N);
    for(ll i = 0; i < N; i++){
        cin >> A[i] >> B[i] >> C[i];
        if(A[i] > C[i]) swap(A[i], C[i]);
    }
    MinCostFlow<ll, ll> g;
    g.add_vertices(N * 4 + 1);
    const ll S = N * 4;
    for(ll i = 0; i < N; i++) g.add_edge(S, i, 0, 1, 0);
    vector<ll> index(N);
    iota(index.begin(), index.end(), 0);
    sort(index.begin(), index.end(), [&](ll x, ll y){ return A[x] < A[y]; });
    for(ll i = 0; i < N; i++){
        auto p = partition_point(index.begin(), index.end(), [&](ll j){ return A[j] <= B[i]; });
        if(p == index.end()) continue;
        g.add_edge(i, *p + N, 0, 1, 0);
    }
    for(ll i = 0; i + 1 < N; i++) g.add_edge(index[i] + N, index[i + 1] + N, 0, N, 0);
    for(ll i = 0; i < N; i++) g.add_edge(i + N, i + N * 3, 0, 1, -C[i]);
    sort(index.begin(), index.end(), [&](ll x, ll y){ return C[x] > C[y]; });
    for(ll i = 0; i < N; i++){
        auto p = partition_point(index.begin(), index.end(), [&](ll j){ return C[j] >= B[i]; });
        if(p == index.end()) continue;
        g.add_edge(i, *p + N * 2, 0, 1, -B[i]);
    }
    for(ll i = 0; i + 1 < N; i++) g.add_edge(index[i] + N * 2, index[i + 1] + N * 2, 0, N, 0);
    for(ll i = 0; i < N; i++) g.add_edge(i + N * 2, i + N * 3, 0, 1, 0);
    for(ll i = 0; i < N; i++) g.add_demand(i + N * 3, 1);
    g.add_supply(S, N);
    const auto status = g.solve().first;
    if(status == Status::INFEASIBLE) return puts("NO") & 0;
    puts("YES");
    puts(-g.get_result_value<ll>() >= M ? "KADOMATSU!" : "NO");
}