AtCoder.MinCostFlow

It solves Minimum-cost flow problem.

Example

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

Minimum cost flow

data McfGraph s cap cost

Min cost flow graph.

Since: 1.0.0.0

Constructor

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

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

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_

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

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

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

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

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

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

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