Library/Graph/Flow/SuccessiveShortestPath.hpp

• View this file on GitHub
• Last update: 2025-06-14 20:53:47+09:00
• Include: #include "Library/Graph/Flow/SuccessiveShortestPath.hpp"

Depends on

• Library/Graph/Graph.hpp

Verified with

• Test/Graph/Flow/SuccessiveShortestPath.test.cpp

Code

#pragma once

#include <deque>

#include <iostream>

#include <map>

#include <queue>

#include <unordered_map>

#include <unordered_set>

#include <vector>


#include "./../Graph.hpp"


namespace mtd {
  template <class Node, class Cap, class Cost>
  class SuccessiveShortestPath {
    // using Node = int;

    // using Cap = int;

    // using Cost = int;


    using GraphCap = std::vector<std::vector<Cap>>;
    using GraphCost = std::vector<std::vector<Cost>>;

    const Graph<Node, std::pair<Cap, Cost>> m_graph;
    const Graph<Node, bool> m_graph_undirected;

    auto construct_graph_undirected() const {
      auto graph_undirected = Graph<Node, bool>(m_graph.size());
      for (const auto& [f, t] : m_graph.getEdgesExcludeCost()) {
        graph_undirected.addEdge(f, t);
      }
      return graph_undirected;
    }

    auto construct_graph_cap() const {
      auto n = m_graph.size();
      GraphCap graph_cap(n, std::vector<Cap>(n));
      for (const auto& [f, t, cc] : m_graph.getEdges()) {
        auto [cap, _] = cc;
        graph_cap[f][t] += cap;
      }
      return graph_cap;
    }
    auto construct_graph_cost() const {
      auto n = m_graph.size();
      GraphCost graph_cost(n, std::vector<Cost>(n));
      for (const auto& [f, t, cc] : m_graph.getEdges()) {
        auto [_, cost] = cc;
        graph_cost[f][t] = cost;
        graph_cost[t][f] = -cost;
      }
      return graph_cost;
    }

    auto update_residual(Node s, Cap rem, GraphCap& residual_cap,
                         GraphCost& residual_cost,
                         const std::deque<Node>& route) const {
      Cost mn = rem;
      auto from = s;
      for (const auto& to : route)
        if (from != to) {
          mn = std::min(mn, residual_cap[from][to]);
          from = to;
        }

      Cost cost_all = 0;
      from = s;
      for (const auto& to : route)
        if (from != to) {
          residual_cap[from][to] -= mn;
          residual_cap[to][from] += mn;
          cost_all += mn * residual_cost[from][to];
          from = to;
        }
      return std::pair<Cap, Cost>{mn, cost_all};
    }

    auto shortest_path_allow_minus(Node s, const GraphCap& residual_cap,
                                   const GraphCost& residual_cost) const {
      auto n = m_graph.size();
      std::vector<Cost> cost(n, 1e18);
      cost[s] = 0;
      for (int _ = 0; _ < n; ++_) {
        for (int from = 0; from < n; ++from) {
          for (const auto& [to, __] : m_graph_undirected.getEdges(from)) {
            if (residual_cap[from][to] > 0) {
              cost[to] =
                  std::min(cost[to], cost[from] + residual_cost[from][to]);
            }
          }
        }
      }
      return cost;
    }

    auto shortest_path(Node s, const GraphCap& residual_cap,
                       const GraphCost& residual_cost,
                       const std::vector<Cost>& p) const {
      using P = std::pair<Cost, Node>;
      std::priority_queue<P, std::vector<P>, std::greater<P>> q;
      std::vector<std::pair<Cost, Node>> min(m_graph.size(), {1e18, -1});
      auto add = [&](Node node, Cost cst, Node from) {
        if (cst >= min[node].first) { return; }
        min[node].first = cst;
        min[node].second = from;
        q.emplace(cst, node);
      };
      add(s, 0, -1);
      while (!q.empty()) {
        auto [nowCost, from] = q.top();
        q.pop();
        if (min[from].first < nowCost) { continue; }
        for (const auto& [to, _] : m_graph_undirected.getEdges(from)) {
          if (residual_cap[from][to] == 0) { continue; }
          auto potential = residual_cost[from][to] + p[from] - p[to];
          add(to, nowCost + potential, from);
        }
      }
      return min;
    }

    static auto restore_route(int t,
                              const std::vector<std::pair<Cost, Node>>& sp) {
      std::deque<Node> route;
      auto now = t;
      while (now > -1) {
        route.emplace_front(now);
        now = sp[now].second;
      }
      return route;
    }

  public:
    /* 単純グラフを仮定 */
    SuccessiveShortestPath(const Graph<Node, std::pair<Cost, Cap>>& graph)
        : m_graph(graph), m_graph_undirected(construct_graph_undirected()) {}

    auto slope(Node s, Node t, Cap c = 1e18) const {
      auto residual_cap = construct_graph_cap();
      auto residual_cost = construct_graph_cost();
      auto default_cost = residual_cost;
      std::deque<std::pair<Cost, Cap>> sl;
      auto p = shortest_path_allow_minus(s, residual_cap, residual_cost);
      auto rem = c;
      while (rem > 0) {
        auto sp = shortest_path(s, residual_cap, default_cost, p);
        auto route = restore_route(t, sp);
        auto [use, cst] =
            update_residual(s, rem, residual_cap, residual_cost, route);
        if (use == 0) { break; }
        sl.emplace_back(use, cst);
        rem -= use;
        for (int i = 0; i < m_graph.size(); ++i) { p[i] += sp[i].first; }
      }
      return sl;
    }

    auto min_cost_max_flow(Node s, Node t, Cap cap = 1e18) const {
      Cap use_all = 0;
      Cost cost_all = 0;
      for (const auto& [u, c] : slope(s, t, cap)) {
        use_all += u;
        cost_all += c;
      }
      return std::pair<Cap, Cost>{use_all, cost_all};
    }
  };
}  // namespace mtd

#line 2 "Library/Graph/Flow/SuccessiveShortestPath.hpp"

#include <deque>

#include <iostream>

#include <map>

#include <queue>

#include <unordered_map>

#include <unordered_set>

#include <vector>


#line 4 "Library/Graph/Graph.hpp"
#include <ranges>

#include <tuple>

#line 7 "Library/Graph/Graph.hpp"

namespace mtd {
  template <class Node = long long, class Cost = long long>
  class Graph {
    using Edge = std::pair<Node, Cost>;
    using Edges = std::vector<Edge>;

    const int m_n;
    std::vector<Edges> m_graph;

  public:
    Graph(int n) : m_n(n), m_graph(n) {}
    Graph(const std::vector<Edges>& edges)
        : m_n(edges.size()), m_graph(edges) {}
    Graph(int n, const std::vector<std::tuple<Node, Node>>& edges,
          bool is_arc = false, bool is_index1 = true)
        : Graph<Node, Cost>(n) {
      for (auto [u, v] : edges) {
        u -= is_index1;
        v -= is_index1;
        if (is_arc) {
          addArc(u, v);
        } else {
          addEdge(u, v);
        }
      }
    }
    Graph(int n, const std::vector<std::tuple<Node, Node, Cost>>& edges,
          bool is_arc = false, bool is_index1 = true)
        : Graph<Node, Cost>(n) {
      for (auto [u, v, c] : edges) {
        u -= is_index1;
        v -= is_index1;
        if (is_arc) {
          addArc(u, v, c);
        } else {
          addEdge(u, v, c);
        }
      }
    }

    auto addEdge(const Node& f, const Node& t, const Cost& c = 1) {
      addArc(f, t, c);
      addArc(t, f, c);
    }
    auto addArc(const Node& f, const Node& t, const Cost& c = 1) {
      m_graph[f].emplace_back(t, c);
    }
    auto getEdges(const Node& from) const {
      class EdgesRange {
        const typename Edges::const_iterator b, e;

      public:
        EdgesRange(const Edges& edges) : b(edges.begin()), e(edges.end()) {}
        auto begin() const { return b; }
        auto end() const { return e; }
      };
      return EdgesRange(m_graph[from]);
    }
    auto getEdges() const {
      std::deque<std::tuple<Node, Node, Cost>> edges;
      for (Node from : std::views::iota(0, m_n)) {
        for (const auto& [to, c] : getEdges(from)) {
          edges.emplace_back(from, to, c);
        }
      }
      return edges;
    }
    auto getEdgesExcludeCost() const {
      std::deque<std::pair<Node, Node>> edges;
      for (Node from : std::views::iota(0, m_n)) {
        for (const auto& [to, _] : getEdges(from)) {
          edges.emplace_back(from, to);
        }
      }
      return edges;
    }
    auto reverse() const {
      auto rev = Graph<Node, Cost>(m_n);
      for (const auto& [from, to, c] : getEdges()) { rev.addArc(to, from, c); }
      return rev;
    }
    auto size() const { return m_n; };
    auto debug(bool directed = false) const {
      for (const auto& [f, t, c] : getEdges()) {
        if (f < t || directed) {
          std::cout << f << " -> " << t << ": " << c << std::endl;
        }
      }
    }
  };
}  // namespace mtd

#line 12 "Library/Graph/Flow/SuccessiveShortestPath.hpp"

namespace mtd {
  template <class Node, class Cap, class Cost>
  class SuccessiveShortestPath {
    // using Node = int;

    // using Cap = int;

    // using Cost = int;


    using GraphCap = std::vector<std::vector<Cap>>;
    using GraphCost = std::vector<std::vector<Cost>>;

    const Graph<Node, std::pair<Cap, Cost>> m_graph;
    const Graph<Node, bool> m_graph_undirected;

    auto construct_graph_undirected() const {
      auto graph_undirected = Graph<Node, bool>(m_graph.size());
      for (const auto& [f, t] : m_graph.getEdgesExcludeCost()) {
        graph_undirected.addEdge(f, t);
      }
      return graph_undirected;
    }

    auto construct_graph_cap() const {
      auto n = m_graph.size();
      GraphCap graph_cap(n, std::vector<Cap>(n));
      for (const auto& [f, t, cc] : m_graph.getEdges()) {
        auto [cap, _] = cc;
        graph_cap[f][t] += cap;
      }
      return graph_cap;
    }
    auto construct_graph_cost() const {
      auto n = m_graph.size();
      GraphCost graph_cost(n, std::vector<Cost>(n));
      for (const auto& [f, t, cc] : m_graph.getEdges()) {
        auto [_, cost] = cc;
        graph_cost[f][t] = cost;
        graph_cost[t][f] = -cost;
      }
      return graph_cost;
    }

    auto update_residual(Node s, Cap rem, GraphCap& residual_cap,
                         GraphCost& residual_cost,
                         const std::deque<Node>& route) const {
      Cost mn = rem;
      auto from = s;
      for (const auto& to : route)
        if (from != to) {
          mn = std::min(mn, residual_cap[from][to]);
          from = to;
        }

      Cost cost_all = 0;
      from = s;
      for (const auto& to : route)
        if (from != to) {
          residual_cap[from][to] -= mn;
          residual_cap[to][from] += mn;
          cost_all += mn * residual_cost[from][to];
          from = to;
        }
      return std::pair<Cap, Cost>{mn, cost_all};
    }

    auto shortest_path_allow_minus(Node s, const GraphCap& residual_cap,
                                   const GraphCost& residual_cost) const {
      auto n = m_graph.size();
      std::vector<Cost> cost(n, 1e18);
      cost[s] = 0;
      for (int _ = 0; _ < n; ++_) {
        for (int from = 0; from < n; ++from) {
          for (const auto& [to, __] : m_graph_undirected.getEdges(from)) {
            if (residual_cap[from][to] > 0) {
              cost[to] =
                  std::min(cost[to], cost[from] + residual_cost[from][to]);
            }
          }
        }
      }
      return cost;
    }

    auto shortest_path(Node s, const GraphCap& residual_cap,
                       const GraphCost& residual_cost,
                       const std::vector<Cost>& p) const {
      using P = std::pair<Cost, Node>;
      std::priority_queue<P, std::vector<P>, std::greater<P>> q;
      std::vector<std::pair<Cost, Node>> min(m_graph.size(), {1e18, -1});
      auto add = [&](Node node, Cost cst, Node from) {
        if (cst >= min[node].first) { return; }
        min[node].first = cst;
        min[node].second = from;
        q.emplace(cst, node);
      };
      add(s, 0, -1);
      while (!q.empty()) {
        auto [nowCost, from] = q.top();
        q.pop();
        if (min[from].first < nowCost) { continue; }
        for (const auto& [to, _] : m_graph_undirected.getEdges(from)) {
          if (residual_cap[from][to] == 0) { continue; }
          auto potential = residual_cost[from][to] + p[from] - p[to];
          add(to, nowCost + potential, from);
        }
      }
      return min;
    }

    static auto restore_route(int t,
                              const std::vector<std::pair<Cost, Node>>& sp) {
      std::deque<Node> route;
      auto now = t;
      while (now > -1) {
        route.emplace_front(now);
        now = sp[now].second;
      }
      return route;
    }

  public:
    /* 単純グラフを仮定 */
    SuccessiveShortestPath(const Graph<Node, std::pair<Cost, Cap>>& graph)
        : m_graph(graph), m_graph_undirected(construct_graph_undirected()) {}

    auto slope(Node s, Node t, Cap c = 1e18) const {
      auto residual_cap = construct_graph_cap();
      auto residual_cost = construct_graph_cost();
      auto default_cost = residual_cost;
      std::deque<std::pair<Cost, Cap>> sl;
      auto p = shortest_path_allow_minus(s, residual_cap, residual_cost);
      auto rem = c;
      while (rem > 0) {
        auto sp = shortest_path(s, residual_cap, default_cost, p);
        auto route = restore_route(t, sp);
        auto [use, cst] =
            update_residual(s, rem, residual_cap, residual_cost, route);
        if (use == 0) { break; }
        sl.emplace_back(use, cst);
        rem -= use;
        for (int i = 0; i < m_graph.size(); ++i) { p[i] += sp[i].first; }
      }
      return sl;
    }

    auto min_cost_max_flow(Node s, Node t, Cap cap = 1e18) const {
      Cap use_all = 0;
      Cost cost_all = 0;
      for (const auto& [u, c] : slope(s, t, cap)) {
        use_all += u;
        cost_all += c;
      }
      return std::pair<Cap, Cost>{use_all, cost_all};
    }
  };
}  // namespace mtd

Back to top page