Safe Haskell	Safe-Inferred
Language	GHC2021

AtCoder.MinCostFlow

Contents

Minimum cost flow
Constructor
Graph building
Flow and slope
Edge information

Description

It solves Minimum-cost flow problem.

Example

Expand

Create min cost flow graph (McfGraph):

>>> import AtCoder.MinCostFlow qualified as MCF
>>> g <- MCF.new @_ {- capacity -} @Int {- cost -} @Int 4

Build a simple graph with addEdge g from to cap cost or addEdge_:

>>> MCF.addEdge g 0 1 2 3    --  0 --> 1     2
0

>>> MCF.addEdge_ g 1 2 2 5   --  0 --> 1 --> 2

Augument flow with flow, maxFlow or slope:

>>> MCF.slope g 0 2 maxBound -- slope g from to flowLimit
[(0,0),(2,16)]

Note that you can't call flow, maxFlow or slope multiple times, or else you'll get wrong return value.

Since: 1.0.0.0

Synopsis

data McfGraph s cap cost
new :: (PrimMonad m, Unbox cap, Unbox cost) => Int -> m (McfGraph (PrimState m) cap cost)
addEdge :: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap, Num cost, Ord cost, Unbox cost) => McfGraph (PrimState m) cap cost -> Int -> Int -> cap -> cost -> m Int
addEdge_ :: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap, Num cost, Ord cost, Unbox cost) => McfGraph (PrimState m) cap cost -> Int -> Int -> cap -> cost -> m ()
flow :: (HasCallStack, PrimMonad m, Integral cap, Ord cap, Unbox cap, Num cost, Ord cost, Bounded cost, Unbox cost) => McfGraph (PrimState m) cap cost -> Int -> Int -> cap -> m (cap, cost)
maxFlow :: (HasCallStack, PrimMonad m, Integral cap, Ord cap, Bounded cap, Unbox cap, Num cost, Ord cost, Bounded cost, Unbox cost) => McfGraph (PrimState m) cap cost -> Int -> Int -> m (cap, cost)
slope :: (HasCallStack, PrimMonad m, Integral cap, Ord cap, Unbox cap, Num cost, Ord cost, Bounded cost, Unbox cost) => McfGraph (PrimState m) cap cost -> Int -> Int -> cap -> m (Vector (cap, cost))
getEdge :: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap, Num cost, Ord cost, Unbox cost) => McfGraph (PrimState m) cap cost -> Int -> m (Int, Int, cap, cap, cost)
edges :: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap, Num cost, Ord cost, Unbox cost) => McfGraph (PrimState m) cap cost -> m (Vector (Int, Int, cap, cap, cost))
unsafeEdges :: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap, Num cost, Ord cost, Unbox cost) => McfGraph (PrimState m) cap cost -> m (Vector (Int, Int, cap, cap, cost))

Minimum cost flow

data McfGraph s cap cost Source #

Min cost flow graph.

Since: 1.0.0.0

Constructor

new :: (PrimMonad m, Unbox cap, Unbox cost) => Int -> m (McfGraph (PrimState m) cap cost) Source #

Creates a directed graph with $n$ vertices and $0$ edges. cap and cost are the type of the capacity and the cost, respectively.

Constraints

$0 \leq n$

Complexity

$O(n)$

Since: 1.0.0.0

Graph building

addEdge Source #

Arguments

:: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap, Num cost, Ord cost, Unbox cost)
=> McfGraph (PrimState m) cap cost	Graph
-> Int	from
-> Int	to
-> cap	capacity
-> cost	cost
-> m Int	Edge index

Adds an edge oriented from from to to with capacity cap and cost cost. It returns an integer $k$ such that this is the $k$ -th edge that is added.

Constraints

$0 \leq \mathrm{from}, \mathrm{to} \lt n$
$0 \leq \mathrm{cap}, \mathrm{cost}$

Complexity

$O(1)$ amortized

Since: 1.0.0.0

addEdge_ Source #

Arguments

:: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap, Num cost, Ord cost, Unbox cost)
=> McfGraph (PrimState m) cap cost	Graph
-> Int	from
-> Int	to
-> cap	capacity
-> cost	cost
-> m ()

addEdge with the return value discarded.

Constraints

$0 \leq \mathrm{from}, \mathrm{to} \lt n$
$0 \leq \mathrm{cap}, \mathrm{cost}$

Complexity

$O(1)$ amortized

Since: 1.0.0.0

Flow and slope

flow Source #

Arguments

:: (HasCallStack, PrimMonad m, Integral cap, Ord cap, Unbox cap, Num cost, Ord cost, Bounded cost, Unbox cost)
=> McfGraph (PrimState m) cap cost	Graph
-> Int	Fource `s`
-> Int	Sink `t`
-> cap	Flow limit
-> m (cap, cost)	Tuple of `(cap, cost`)

Augments the flow from $s$ to $t$ as much as possible, until reaching the amount of flowLimit. It returns the amount of the flow and the cost.

Constraints

Same as slope.

Complexity

Same as slope.

Since: 1.0.0.0

maxFlow Source #

Arguments

:: (HasCallStack, PrimMonad m, Integral cap, Ord cap, Bounded cap, Unbox cap, Num cost, Ord cost, Bounded cost, Unbox cost)
=> McfGraph (PrimState m) cap cost	Graph
-> Int	Source `s`
-> Int	Sink `t`
-> m (cap, cost)	Tuple of `(cap, cost`)

flow with no capacity limit.

Constraints

Same as slope.

Complexity

Same as slope.

Since: 1.0.0.0

slope Source #

Arguments

:: (HasCallStack, PrimMonad m, Integral cap, Ord cap, Unbox cap, Num cost, Ord cost, Bounded cost, Unbox cost)
=> McfGraph (PrimState m) cap cost	Graph
-> Int	Source `s`
-> Int	Sink `t`
-> cap	Flow limit
-> m (Vector (cap, cost))	Vector of `(cap, cost)`

Let $g$ be a function such that $g(x)$ is the cost of the minimum cost $s-t$ flow when the amount of the flow is exactly $x$ . $g$ is known to be piecewise linear.

The first element of the list is $(0, 0)$ .
Both of first and second tuple elements are strictly increasing.
No three changepoints are on the same line.
The last element of the list is $y, g(y))$ , where $y = \min(x, \mathrm{flowLimit})$ .

Constraints

Let $x$ be the maximum cost among all edges.

$s \neq t$
$0 \leq s, t \lt n$
You can't call slope, flow or maxFlow multiple times.
The total amount of the flow is in cap.
The total cost of the flow is in cost.
$0 \leq nx \leq 8 \times 10^{18} + 1000$

Complexity

$O(F (n + m) \log (n + m))$ , where $F$ is the amount of the flow and $m$ is the number of added edges.

Since: 1.0.0.0

Edge information

getEdge Source #

Arguments

:: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap, Num cost, Ord cost, Unbox cost)
=> McfGraph (PrimState m) cap cost	Graph
-> Int	Edge index
-> m (Int, Int, cap, cap, cost)	Tuple of `(from, to, cap, flow, cost)`

Returns the current internal state of the edges: (from, to, cap, flow, cost). The edges are ordered in the same order as added by addEdge.

Constraints

$0 \leq i \lt m$

Complexity

$O(1)$

Since: 1.0.0.0

edges Source #

Arguments

:: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap, Num cost, Ord cost, Unbox cost)
=> McfGraph (PrimState m) cap cost	Graph
-> m (Vector (Int, Int, cap, cap, cost))	Vector of `(from, to, cap, flow, cost)`

Returns the current internal state of the edges: (from, to, cap, flow, cost). The edges are ordered in the same order as added by addEdge.

Complexity

$O(m)$ , where $m$ is the number of added edges.

Since: 1.0.0.0

unsafeEdges Source #

Arguments

:: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap, Num cost, Ord cost, Unbox cost)
=> McfGraph (PrimState m) cap cost	Graph
-> m (Vector (Int, Int, cap, cap, cost))	Vector of `(from, to, cap, flow, cost)`

Returns the current internal state of the edges: (from, to, cap, flow, cost), but without making copy. The edges are ordered in the same order as added by addEdge.

Complexity

$O(1)$

Since: 1.0.0.0

Key	Shortcut
s	Open this search box
esc	Close this search box
↓,ctrl + j	Move down in search results
↑,ctrl + k	Move up in search results
↵	Go to active search result