flow/k_ary_optimization.hpp

• View this file on GitHub
• Last update: 2025-10-13 18:56:57+09:00
• Include: #include "flow/k_ary_optimization.hpp"

Depends on

• flow/maxflow.hpp

Code

#include "flow/maxflow.hpp"

// ABC347G
template <typename T, bool MINIMIZE>
struct K_ary_Optimization {
  int n;
  vc<int> ks;
  vvc<int> idx;
  map<pair<int, int>, T> edges;
  int source, sink, nxt;
  T base_cost;

  // idx[i][j] が cut の source 側：val[i]>=j
  K_ary_Optimization(vc<int> ks) : n(len(ks)), ks(ks), base_cost(0) {
    source = 0, sink = 1, nxt = 2;
    for (auto& k: ks) {
      assert(k >= 1);
      vc<int> I(k + 1);
      I[0] = source, I[k] = sink;
      FOR(i, 1, k) { I[i] = nxt++; }
      idx.eb(I);
      if (k >= 3) { FOR(j, 1, k - 1) add_edge(I[j + 1], I[j], infty<T>); }
    }
  }

  // xi を 0, 1, ..., k-1 にするときにかかるコストを追加する。
  void add_1(int i, vc<T> cost) {
    assert(0 <= i && i < n && len(cost) == ks[i]);
    if (!MINIMIZE) {
      for (auto& x: cost) x = -x;
    }
    _add_1(i, cost);
  }

  void add_2(int i, int j, vvc<T> cost) {
    assert(0 <= i && i < n && 0 <= j && j < n && i != j);
    int H = ks[i], W = ks[j];
    assert(len(cost) == H);
    FOR(a, H) assert(len(cost[a]) == W);
    if (!MINIMIZE) { FOR(a, H) FOR(b, W) cost[a][b] = -cost[a][b]; }
    _add_2(i, j, cost);
  }

  // 最小値および、[0,k) 列を返す
  pair<T, vc<int>> calc() {
    MaxFlow<T> G(nxt, source, sink);
    for (auto&& [key, cap]: edges) {
      auto [frm, to] = key;
      G.add(frm, to, cap);
    }

    auto [val, cut] = G.cut();
    val += base_cost;
    vc<int> ANS(n);
    FOR(i, n) {
      FOR(j, 1, ks[i]) { ANS[i] += 1 - cut[idx[i][j]]; }
    }
    if (!MINIMIZE) val = -val;
    return {val, ANS};
  }

private:
  void add_base(T x) {
    base_cost += x;
    assert(-infty<T> < base_cost && base_cost < infty<T>);
  }

  void add_edge(int i, int j, T t) {
    assert(t >= 0);
    if (t == 0) return;
    pair<int, int> key = mp(i, j);
    edges[key] += t;
    assert(edges[key] <= infty<T>);
  }

  void _add_1(int i, vc<T> cost) {
    add_base(cost[0]);
    FOR_R(j, ks[i]) cost[j] -= cost[0];
    FOR(j, 1, ks[i]) {
      T x = cost[j] - cost[j - 1];
      // j 以上にすると x
      if (x > 0) add_edge(idx[i][j], sink, x);
      if (x < 0) add_base(x), add_edge(source, idx[i][j], -x);
    }
  }
  void _add_2(int i, int j, vvc<T> cost) {
    int H = ks[i], W = ks[j];
    _add_1(j, cost[0]);
    FOR_R(a, H) FOR(b, W) cost[a][b] -= cost[0][b];
    vc<T> tmp(H);
    FOR(a, H) tmp[a] = cost[a][W - 1];
    _add_1(i, tmp);
    FOR(a, H) FOR(b, W) cost[a][b] -= tmp[a];
    FOR(a, 1, H) FOR(b, W - 1) {
      T x = cost[a][b] + cost[a - 1][b + 1] - cost[a - 1][b] - cost[a][b + 1];
      assert(x >= 0); // monge
      add_edge(idx[i][a], idx[j][b + 1], x);
    }
  }
};

#line 1 "flow/k_ary_optimization.hpp"

#line 1 "flow/maxflow.hpp"
template <typename Cap>
struct MaxFlow {
  struct Edge {
    int to, rev;
    Cap cap;
  };

  vc<Edge> edges;
  vc<int> indptr, level;
  vc<Cap> init_cap;
  vc<tuple<int, int, Cap, Cap>> edge_pool;

  const int N, source, sink;
  bool calculated;
  Cap flow_ans;
  vc<int> pos;

  MaxFlow(int N, int source, int sink)
      : N(N), source(source), sink(sink), calculated(0), flow_ans(0) {}

  void add(int frm, int to, Cap cap, Cap rev_cap = 0) {
    calculated = 0;
    assert(0 <= frm && frm < N);
    assert(0 <= to && to < N);
    assert(Cap(0) <= cap);
    edge_pool.eb(frm, to, cap, rev_cap);
  }

  void build_csr() {
    int M = len(edge_pool);
    indptr.assign(N + 1, 0);
    for (auto [a, b, c, d] : edge_pool) indptr[a + 1]++, indptr[b + 1]++;
    FOR(i, N) indptr[i + 1] += indptr[i];
    vc<int> prog = indptr;
    edges.resize(2 * M);
    init_cap.resize(2 * M);
    for (auto [a, b, c, d] : edge_pool) {
      int I1 = prog[a], I2 = prog[b];
      edges[I1] = Edge{b, I2, c}, init_cap[I1] = c, prog[a]++;
      edges[I2] = Edge{a, I1, d}, init_cap[I2] = d, prog[b]++;
      pos.eb(I1);
    }
  }

  Cap flow() {
    if (calculated) return flow_ans;
    calculated = true;
    if (indptr.empty()) build_csr();
    vc<int> prog = indptr;
    level.resize(N);
    vc<int> que(N);
    auto bfs = [&]() -> void {
      fill(all(level), -1);
      int ql = 0, qr = 0;
      level[source] = 0, que[qr++] = source;
      while (ql < qr) {
        int v = que[ql++];
        FOR(i, indptr[v], indptr[v + 1]) {
          Edge& e = edges[i];
          if (e.cap > 0 && level[e.to] == -1) {
            level[e.to] = level[v] + 1;
            que[qr++] = e.to;
            if (e.to == sink) return;
          }
        }
      }
    };

    // ACL 参考. v までいくつ流してくるという方式.
    // source-sink上にあるところだけ探索するのでこちらの方が高速ということだと思う.
    auto dfs = [&](auto& dfs, int v, Cap lim) -> Cap {
      if (v == source) return lim;
      Cap res = 0;
      int nxt_lv = level[v] - 1;
      for (int& i = prog[v]; i < indptr[v + 1]; ++i) {
        auto& e = edges[i];
        if (level[e.to] != nxt_lv || edges[e.rev].cap == 0) continue;
        Cap a = dfs(dfs, e.to, min(lim - res, edges[e.rev].cap));
        if (a <= 0) continue;
        e.cap += a, edges[e.rev].cap -= a, res += a;
        if (res == lim) return res;
      }
      level[v] = N;
      return res;
    };
    while (1) {
      bfs();
      if (level[sink] == -1) break;
      copy(all(indptr), prog.begin());
      Cap x = dfs(dfs, sink, infty<Cap>);
      flow_ans += x;
      if (flow_ans >= infty<Cap>) return infty<Cap>;
    }
    return flow_ans;
  }

  void change_capacity(int i, Cap after) {
    i = pos[i];
    auto& e = edges[i];
    Cap before = init_cap[i];
    Cap f = before - e.cap;
    init_cap[i] = after;
    if (before < after) {
      calculated = (e.cap > 0);
      e.cap += after - before;
      return;
    }
    e.cap = after - f;
    // 差分を押し戻す処理発生
    if (e.cap < 0) flow_push_back(e);
  }

  void flow_push_back(Edge& e0) {
    auto& re0 = edges[e0.rev];
    int a = re0.to;
    int b = e0.to;
    /*
    辺 e0 の容量が正になるように戻す
    path-cycle 分解を考えれば、
    - uv 辺を含むサイクルを消す
    - suvt パスを消す
    前者は残余グラフで ab パス（flow_ans が変わらない）
    後者は残余グラフで tb, as パス
    */

    vc<int> prog(N + 1);
    auto find_path = [&](int s, int t, Cap lim) -> Cap {
      vc<bool> vis(N);
      copy(all(indptr), prog.begin());
      auto dfs = [&](auto& dfs, int v, Cap f) -> Cap {
        if (v == t) return f;
        for (int& i = prog[v]; i < indptr[v + 1]; ++i) {
          auto& e = edges[i];
          if (vis[e.to] || e.cap <= Cap(0)) continue;
          vis[e.to] = 1;
          Cap a = dfs(dfs, e.to, min(f, e.cap));
          assert(a >= 0);
          if (a == Cap(0)) continue;
          e.cap -= a, edges[e.rev].cap += a;
          return a;
        }
        return 0;
      };
      return dfs(dfs, s, lim);
    };

    while (e0.cap < 0) {
      Cap x = find_path(a, b, -e0.cap);
      if (x == Cap(0)) break;
      e0.cap += x, re0.cap -= x;
    }
    Cap c = -e0.cap;
    while (c > 0 && a != source) {
      Cap x = find_path(a, source, c);
      assert(x > 0);
      c -= x;
    }
    c = -e0.cap;
    while (c > 0 && b != sink) {
      Cap x = find_path(sink, b, c);
      assert(x > 0);
      c -= x;
    }
    c = -e0.cap;
    e0.cap += c, re0.cap -= c;
    flow_ans -= c;
  }

  // frm, to, flow
  vc<tuple<int, int, Cap>> get_flow_edges() {
    vc<tuple<int, int, Cap>> res;
    FOR(v, N) {
      FOR(i, indptr[v], indptr[v + 1]) {
        Edge& e = edges[i];
        Cap f = init_cap[i] - e.cap;
        if (f > 0) res.eb(v, e.to, f);
      }
    }
    return res;
  }

  // 最小カットの値および、カットを表す 01 列を返す
  pair<Cap, vc<int>> cut() {
    flow();
    vc<int> res(N);
    FOR(v, N) res[v] = (level[v] >= 0 ? 0 : 1);
    return {flow_ans, res};
  }

  // O(F(N+M)) くらい使って経路復元
  // simple path になる
  vvc<int> path_decomposition() {
    flow();
    auto edges = get_flow_edges();
    vvc<int> TO(N);
    for (auto&& [frm, to, flow] : edges) {
      FOR(flow) TO[frm].eb(to);
    }
    vvc<int> res;
    vc<int> vis(N);

    FOR(flow_ans) {
      vc<int> path = {source};
      vis[source] = 1;
      while (path.back() != sink) {
        int to = POP(TO[path.back()]);
        while (vis[to]) {
          vis[POP(path)] = 0;
        }
        path.eb(to), vis[to] = 1;
      }
      for (auto&& v : path) vis[v] = 0;
      res.eb(path);
    }
    return res;
  }

  void debug() {
#ifdef LOCAL
    print("source", source);
    print("sink", sink);
    print("edges (frm, to, cap, flow)");
    FOR(v, N) {
      FOR(i, indptr[v], indptr[v + 1]) {
        Edge& e = edges[i];
        Cap f = init_cap[i] - e.cap;
        SHOW(i, v, e.to, e.cap, f);
      }
    }
#endif
  }
};
#line 3 "flow/k_ary_optimization.hpp"

// ABC347G
template <typename T, bool MINIMIZE>
struct K_ary_Optimization {
  int n;
  vc<int> ks;
  vvc<int> idx;
  map<pair<int, int>, T> edges;
  int source, sink, nxt;
  T base_cost;

  // idx[i][j] が cut の source 側：val[i]>=j
  K_ary_Optimization(vc<int> ks) : n(len(ks)), ks(ks), base_cost(0) {
    source = 0, sink = 1, nxt = 2;
    for (auto& k: ks) {
      assert(k >= 1);
      vc<int> I(k + 1);
      I[0] = source, I[k] = sink;
      FOR(i, 1, k) { I[i] = nxt++; }
      idx.eb(I);
      if (k >= 3) { FOR(j, 1, k - 1) add_edge(I[j + 1], I[j], infty<T>); }
    }
  }

  // xi を 0, 1, ..., k-1 にするときにかかるコストを追加する。
  void add_1(int i, vc<T> cost) {
    assert(0 <= i && i < n && len(cost) == ks[i]);
    if (!MINIMIZE) {
      for (auto& x: cost) x = -x;
    }
    _add_1(i, cost);
  }

  void add_2(int i, int j, vvc<T> cost) {
    assert(0 <= i && i < n && 0 <= j && j < n && i != j);
    int H = ks[i], W = ks[j];
    assert(len(cost) == H);
    FOR(a, H) assert(len(cost[a]) == W);
    if (!MINIMIZE) { FOR(a, H) FOR(b, W) cost[a][b] = -cost[a][b]; }
    _add_2(i, j, cost);
  }

  // 最小値および、[0,k) 列を返す
  pair<T, vc<int>> calc() {
    MaxFlow<T> G(nxt, source, sink);
    for (auto&& [key, cap]: edges) {
      auto [frm, to] = key;
      G.add(frm, to, cap);
    }

    auto [val, cut] = G.cut();
    val += base_cost;
    vc<int> ANS(n);
    FOR(i, n) {
      FOR(j, 1, ks[i]) { ANS[i] += 1 - cut[idx[i][j]]; }
    }
    if (!MINIMIZE) val = -val;
    return {val, ANS};
  }

private:
  void add_base(T x) {
    base_cost += x;
    assert(-infty<T> < base_cost && base_cost < infty<T>);
  }

  void add_edge(int i, int j, T t) {
    assert(t >= 0);
    if (t == 0) return;
    pair<int, int> key = mp(i, j);
    edges[key] += t;
    assert(edges[key] <= infty<T>);
  }

  void _add_1(int i, vc<T> cost) {
    add_base(cost[0]);
    FOR_R(j, ks[i]) cost[j] -= cost[0];
    FOR(j, 1, ks[i]) {
      T x = cost[j] - cost[j - 1];
      // j 以上にすると x
      if (x > 0) add_edge(idx[i][j], sink, x);
      if (x < 0) add_base(x), add_edge(source, idx[i][j], -x);
    }
  }
  void _add_2(int i, int j, vvc<T> cost) {
    int H = ks[i], W = ks[j];
    _add_1(j, cost[0]);
    FOR_R(a, H) FOR(b, W) cost[a][b] -= cost[0][b];
    vc<T> tmp(H);
    FOR(a, H) tmp[a] = cost[a][W - 1];
    _add_1(i, tmp);
    FOR(a, H) FOR(b, W) cost[a][b] -= tmp[a];
    FOR(a, 1, H) FOR(b, W - 1) {
      T x = cost[a][b] + cost[a - 1][b + 1] - cost[a - 1][b] - cost[a][b + 1];
      assert(x >= 0); // monge
      add_edge(idx[i][a], idx[j][b + 1], x);
    }
  }
};

Back to top page