| Safe Haskell | None |
|---|---|
| Language | GHC2021 |
AtCoder.MinCostFlow
Description
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 costaddEdge_:
>>>MCF.addEdge g 0 1 2 3 -- 0 --> 1 20>>>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
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
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
Graph building
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 #
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
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 () #
addEdge with 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
Flow and slope
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)) #
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,flowormaxFlowmultiple 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
Edge information
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) #
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
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)) #
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
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)) #
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