tmk::place::MinCostFlow Class Reference

Min-cost flow on a small graph (exposed for tests). More...

#include <place/lower_bound.hpp>

Public Member Functions
	MinCostFlow (int n)
void	add_arc (int u, int v, std::int64_t cost, std::int64_t cap=kInf)
std::pair< std::int64_t, std::int64_t >	solve (int s, int t, std::int64_t limit)
	Sends up to limit units from s to t at minimum cost; returns {flow, cost}.

Static Public Attributes
static constexpr std::int64_t	kInf = INT64_MAX / 4

Detailed Description

Min-cost flow on a small graph (exposed for tests).

Successive shortest paths with Dijkstra and potentials; arcs from add_arc have infinite capacity unless cap is given. Costs are integers.

Definition at line 30 of file lower_bound.hpp.

Constructor & Destructor Documentation

MinCostFlow()

tmk::place::MinCostFlow::MinCostFlow ( int n )

inlineexplicit

Definition at line 32 of file lower_bound.hpp.

Member Function Documentation

add_arc()

void tmk::place::MinCostFlow::add_arc	(	int	u,
		int	v,
		std::int64_t	cost,
		std::int64_t	cap = kInf )

solve()

std::pair< std::int64_t, std::int64_t > tmk::place::MinCostFlow::solve	(	int	s,
		int	t,
		std::int64_t	limit )

Sends up to limit units from s to t at minimum cost; returns {flow, cost}.

The graph must have no negative cycle; negative arc costs are allowed (initial potentials by Bellman–Ford).

Member Data Documentation

kInf

std::int64_t tmk::place::MinCostFlow::kInf = INT64_MAX / 4

staticconstexpr

Definition at line 33 of file lower_bound.hpp.

---

The documentation for this class was generated from the following file:

• place/lower_bound.hpp