{-# LANGUAGE RecordWildCards #-}

-- | It solves [maximum flow problem](https://en.wikipedia.org/wiki/Maximum_flow_problem).
--
-- ==== __Example__
-- Create a max flow graph (`MfGraph`):
--
-- >>> import AtCoder.MaxFlow qualified as MF
-- >>> g <- MF.new @_ @Int 3        --  0     1     2
--
-- Build a simple graph with @'addEdge' g from to cap@ or `addEdge_`:
--
-- >>> MF.addEdge g 0 1 (2 :: Int)  --  0 --> 1     2
-- 0
--
-- >>> MF.addEdge_ g 1 2 (1 :: Int) --  0 --> 1 --> 2
--
-- Augument the flow with `flow`. `maxFlow` can also be used when there's no flow limit:
--
-- >>> MF.flow g 0 2 {- flowLimit -} maxBound -- same as `MF.maxFlow g 0 2`
-- 1
--
-- Get the minimum cut with `minCut`. In this case, removing the second edge makes the minimum cut
-- (note that the edge capacity \(1\) = max flow):
--
-- >>> MF.minCut g 0 -- returns a Bit vector. `1` (`Bit True`) is on the `s` side.
-- [1,1,0]
--
-- Retrieve the edge state with `getEdge`. We can confirm the flow is @1@:
--
-- >>> MF.getEdge g 0 -- returns (from, to, cap, flow)
-- (0,1,2,1)
--
-- @since 1.0.0.0
module AtCoder.MaxFlow
  ( -- * Max flow graph
    MfGraph (nG),

    -- * Constructor
    new,

    -- * Graph building
    addEdge,
    addEdge_,
    getEdge,

    -- * Flow operations
    flow,
    maxFlow,

    -- * Minimum cut
    minCut,

    -- * Edge information
    edges,
    changeEdge,
  )
where

-- TODO: add `build`.

import AtCoder.Internal.Assert qualified as ACIA
import AtCoder.Internal.GrowVec qualified as ACIGV
import AtCoder.Internal.Queue qualified as ACIQ
import Control.Monad (unless, when)
import Control.Monad.Fix (fix)
import Control.Monad.Primitive (PrimMonad, PrimState)
import Data.Bit (Bit (..))
import Data.Primitive.MutVar (readMutVar)
import Data.Vector qualified as V
import Data.Vector.Generic qualified as VG
import Data.Vector.Generic.Mutable qualified as VGM
import Data.Vector.Unboxed qualified as VU
import Data.Vector.Unboxed.Mutable qualified as VUM
import GHC.Stack (HasCallStack)

-- | Max flow graph.
--
-- @since 1.0.0.0
data MfGraph s cap = MfGraph
  { -- | The number of vertices.
    --
    -- @since 1.0.0.0
    forall s cap. MfGraph s cap -> Int
nG :: {-# UNPACK #-} !Int,
    -- | MfGraph: fromVertex -> vector of @(toVertex, revEdgeIndex, capacity)@.
    forall s cap. MfGraph s cap -> Vector (GrowVec s (Int, Int, cap))
gG :: !(V.Vector (ACIGV.GrowVec s (Int, Int, cap))),
    -- | Forward edge information: originalEdgeIndex -> (fromVertex, edgeIndex)
    forall s cap. MfGraph s cap -> GrowVec s (Int, Int)
posG :: !(ACIGV.GrowVec s (Int, Int))
  }

-- | Creates a graph of \(n\) vertices and \(0\) edges. `cap` is the type of the capacity.
--
-- ==== Constraints
-- - \(0 \leq n\)
--
-- ==== Complexity
-- - \(O(n)\)
--
-- @since 1.0.0.0
{-# INLINE new #-}
new :: (PrimMonad m, VU.Unbox cap) => Int -> m (MfGraph (PrimState m) cap)
new :: forall (m :: * -> *) cap.
(PrimMonad m, Unbox cap) =>
Int -> m (MfGraph (PrimState m) cap)
new Int
nG = do
  Vector (GrowVec (PrimState m) (Int, Int, cap))
gG <- Int
-> m (GrowVec (PrimState m) (Int, Int, cap))
-> m (Vector (GrowVec (PrimState m) (Int, Int, cap)))
forall (m :: * -> *) a. Monad m => Int -> m a -> m (Vector a)
V.replicateM Int
nG (Int -> m (GrowVec (PrimState m) (Int, Int, cap))
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (GrowVec (PrimState m) a)
ACIGV.new Int
0)
  GrowVec (PrimState m) (Int, Int)
posG <- Int -> m (GrowVec (PrimState m) (Int, Int))
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (GrowVec (PrimState m) a)
ACIGV.new Int
0
  MfGraph (PrimState m) cap -> m (MfGraph (PrimState m) cap)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure MfGraph {Int
Vector (GrowVec (PrimState m) (Int, Int, cap))
GrowVec (PrimState m) (Int, Int)
nG :: Int
gG :: Vector (GrowVec (PrimState m) (Int, Int, cap))
posG :: GrowVec (PrimState m) (Int, Int)
nG :: Int
gG :: Vector (GrowVec (PrimState m) (Int, Int, cap))
posG :: GrowVec (PrimState m) (Int, Int)
..}

-- | Adds an edge oriented from the vertex @from@ to the vertex @to@ with the capacity @cap@ and the
-- flow amount \(0\). 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}\)
--
-- ==== Complexity
-- - \(O(1)\) amortized
--
-- @since 1.0.0.0
{-# INLINE addEdge #-}
addEdge ::
  (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap) =>
  -- | Graph
  MfGraph (PrimState m) cap ->
  -- | from
  Int ->
  -- | to
  Int ->
  -- | cap
  cap ->
  -- | Edge index
  m Int
addEdge :: forall (m :: * -> *) cap.
(HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) =>
MfGraph (PrimState m) cap -> Int -> Int -> cap -> m Int
addEdge MfGraph {Int
Vector (GrowVec (PrimState m) (Int, Int, cap))
GrowVec (PrimState m) (Int, Int)
nG :: forall s cap. MfGraph s cap -> Int
gG :: forall s cap. MfGraph s cap -> Vector (GrowVec s (Int, Int, cap))
posG :: forall s cap. MfGraph s cap -> GrowVec s (Int, Int)
nG :: Int
gG :: Vector (GrowVec (PrimState m) (Int, Int, cap))
posG :: GrowVec (PrimState m) (Int, Int)
..} Int
from Int
to cap
cap = do
  let !()
_ = HasCallStack => String -> String -> Int -> String -> Int -> ()
String -> String -> Int -> String -> Int -> ()
ACIA.checkCustom String
"AtCoder.MaxFlow.addEdge" String
"`from` vertex" Int
from String
"the number of vertices" Int
nG
  let !()
_ = HasCallStack => String -> String -> Int -> String -> Int -> ()
String -> String -> Int -> String -> Int -> ()
ACIA.checkCustom String
"AtCoder.MaxFlow.addEdge" String
"`to` vertex" Int
to String
"the number of vertices" Int
nG
  let !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (cap
0 cap -> cap -> Bool
forall a. Ord a => a -> a -> Bool
<= cap
cap) String
"AtCoder.MaxFlow.addEdge: given invalid edge `cap` less than `0`" -- not `Show cap`
  Int
m <- GrowVec (PrimState m) (Int, Int) -> m Int
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> m Int
ACIGV.length GrowVec (PrimState m) (Int, Int)
posG
  Int
iEdge <- GrowVec (PrimState m) (Int, Int, cap) -> m Int
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> m Int
ACIGV.length (Vector (GrowVec (PrimState m) (Int, Int, cap))
gG Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> GrowVec (PrimState m) (Int, Int, cap)
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
from)
  GrowVec (PrimState m) (Int, Int) -> (Int, Int) -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> a -> m ()
ACIGV.pushBack GrowVec (PrimState m) (Int, Int)
posG (Int
from, Int
iEdge)
  Int
iRevEdge <- do
    Int
len <- GrowVec (PrimState m) (Int, Int, cap) -> m Int
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> m Int
ACIGV.length (Vector (GrowVec (PrimState m) (Int, Int, cap))
gG Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> GrowVec (PrimState m) (Int, Int, cap)
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
to)
    Int -> m Int
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int -> m Int) -> Int -> m Int
forall a b. (a -> b) -> a -> b
$ if Int
from Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
to then Int
len Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 else Int
len
  GrowVec (PrimState m) (Int, Int, cap) -> (Int, Int, cap) -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> a -> m ()
ACIGV.pushBack (Vector (GrowVec (PrimState m) (Int, Int, cap))
gG Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> GrowVec (PrimState m) (Int, Int, cap)
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
from) (Int
to, Int
iRevEdge, cap
cap)
  GrowVec (PrimState m) (Int, Int, cap) -> (Int, Int, cap) -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> a -> m ()
ACIGV.pushBack (Vector (GrowVec (PrimState m) (Int, Int, cap))
gG Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> GrowVec (PrimState m) (Int, Int, cap)
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
to) (Int
from, Int
iEdge, cap
0)
  Int -> m Int
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
m

-- | `addEdge` with the return value discarded.
--
-- ==== Constraints
-- - \(0 \leq \mathrm{from}, \mathrm{to} \lt n\)
-- - \(0 \leq \mathrm{cap}\)
--
-- ==== Complexity
-- - \(O(1)\) amortized
--
-- @since 1.0.0.0
{-# INLINE addEdge_ #-}
addEdge_ ::
  (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap) =>
  -- | Graph
  MfGraph (PrimState m) cap ->
  -- | from
  Int ->
  -- | to
  Int ->
  -- | cap
  cap ->
  m ()
addEdge_ :: forall (m :: * -> *) cap.
(HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) =>
MfGraph (PrimState m) cap -> Int -> Int -> cap -> m ()
addEdge_ MfGraph (PrimState m) cap
graph Int
from Int
to cap
cap = do
  Int
_ <- MfGraph (PrimState m) cap -> Int -> Int -> cap -> m Int
forall (m :: * -> *) cap.
(HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) =>
MfGraph (PrimState m) cap -> Int -> Int -> cap -> m Int
addEdge MfGraph (PrimState m) cap
graph Int
from Int
to cap
cap
  () -> m ()
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()

-- | Augments the flow from \(s\) to \(t\) as much as possible, until reaching the amount of
-- @flowLimit@. It returns the amount of the flow augmented. You may call it multiple times.
--
-- ==== Constraints
-- - \(s \neq t\)
-- - \(0 \leq s, t \lt n\)
--
-- ==== Complexity
-- - \(O((n + m) \sqrt{m})\) (if all the capacities are \(1\)),
-- - \(O(n^2 m)\) (general), or
-- - \(O(F(n + m))\), where \(F\) is the returned value
--
-- @since 1.0.0.0
{-# INLINE flow #-}
flow ::
  (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap) =>
  -- | Graph
  MfGraph (PrimState m) cap ->
  -- | Source @s@
  Int ->
  -- | Sink @t@
  Int ->
  -- | Flow limit
  cap ->
  -- | Max flow
  m cap
flow :: forall (m :: * -> *) cap.
(HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) =>
MfGraph (PrimState m) cap -> Int -> Int -> cap -> m cap
flow MfGraph {Int
Vector (GrowVec (PrimState m) (Int, Int, cap))
GrowVec (PrimState m) (Int, Int)
nG :: forall s cap. MfGraph s cap -> Int
gG :: forall s cap. MfGraph s cap -> Vector (GrowVec s (Int, Int, cap))
posG :: forall s cap. MfGraph s cap -> GrowVec s (Int, Int)
nG :: Int
gG :: Vector (GrowVec (PrimState m) (Int, Int, cap))
posG :: GrowVec (PrimState m) (Int, Int)
..} Int
s Int
t cap
flowLimit = do
  let !()
_ = HasCallStack => String -> String -> Int -> String -> Int -> ()
String -> String -> Int -> String -> Int -> ()
ACIA.checkCustom String
"AtCoder.MaxFlow.flow" String
"`source` vertex" Int
s String
"the number of vertices" Int
nG
  let !()
_ = HasCallStack => String -> String -> Int -> String -> Int -> ()
String -> String -> Int -> String -> Int -> ()
ACIA.checkCustom String
"AtCoder.MaxFlow.flow" String
"`sink` vertex" Int
t String
"the number of vertices" Int
nG
  let !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (Int
s Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
t) (String -> ()) -> String -> ()
forall a b. (a -> b) -> a -> b
$ String
"AtCoder.MaxFlow.flow: `source` and `sink` vertex must be distinct: `" String -> String -> String
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
s String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
"`"

  MVector (PrimState m) Int
level <- Int -> m (MVector (PrimState m) Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
nG
  Queue (PrimState m) Int
que <- Int -> m (Queue (PrimState m) Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (Queue (PrimState m) a)
ACIQ.new Int
nG
  let bfs :: m ()
bfs = do
        MVector (PrimState m) Int -> Int -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> a -> m ()
VGM.set MVector (PrimState m) Int
level (-Int
1 :: Int)
        MVector (PrimState m) Int -> Int -> Int -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Int
level Int
s Int
0
        Queue (PrimState m) Int -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> m ()
ACIQ.clear Queue (PrimState m) Int
que
        Queue (PrimState m) Int -> Int -> m ()
forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> a -> m ()
ACIQ.pushBack Queue (PrimState m) Int
que Int
s
        (m () -> m ()) -> m ()
forall a. (a -> a) -> a
fix ((m () -> m ()) -> m ()) -> (m () -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \m ()
loop -> do
          Maybe Int
v_ <- Queue (PrimState m) Int -> m (Maybe Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> m (Maybe a)
ACIQ.popFront Queue (PrimState m) Int
que
          case Maybe Int
v_ of
            Maybe Int
Nothing -> () -> m ()
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
            Just Int
v -> do
              (VUM.MV_3 Int
_ MVector (PrimState m) Int
vecTo MVector (PrimState m) Int
_ MVector (PrimState m) cap
vecCap) <- MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap))
-> m (MVector (PrimState m) (Int, Int, cap))
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar (MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap))
 -> m (MVector (PrimState m) (Int, Int, cap)))
-> MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap))
-> m (MVector (PrimState m) (Int, Int, cap))
forall a b. (a -> b) -> a -> b
$ GrowVec (PrimState m) (Int, Int, cap)
-> MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap))
forall s a. GrowVec s a -> MutVar s (MVector s a)
ACIGV.vecGV (Vector (GrowVec (PrimState m) (Int, Int, cap))
gG Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> GrowVec (PrimState m) (Int, Int, cap)
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
v)
              Int
len <- GrowVec (PrimState m) (Int, Int, cap) -> m Int
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> m Int
ACIGV.length (Vector (GrowVec (PrimState m) (Int, Int, cap))
gG Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> GrowVec (PrimState m) (Int, Int, cap)
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
v)
              Vector (Int, cap)
neighbors <- Vector Int -> Vector cap -> Vector (Int, cap)
forall a b.
(Unbox a, Unbox b) =>
Vector a -> Vector b -> Vector (a, b)
VU.zip (Vector Int -> Vector cap -> Vector (Int, cap))
-> m (Vector Int) -> m (Vector cap -> Vector (Int, cap))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState m) Int -> m (Vector Int)
forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> m (Vector a)
VU.unsafeFreeze (Int -> MVector (PrimState m) Int -> MVector (PrimState m) Int
forall a s. Unbox a => Int -> MVector s a -> MVector s a
VUM.take Int
len MVector (PrimState m) Int
vecTo) m (Vector cap -> Vector (Int, cap))
-> m (Vector cap) -> m (Vector (Int, cap))
forall a b. m (a -> b) -> m a -> m b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> MVector (PrimState m) cap -> m (Vector cap)
forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> m (Vector a)
VU.unsafeFreeze (Int -> MVector (PrimState m) cap -> MVector (PrimState m) cap
forall a s. Unbox a => Int -> MVector s a -> MVector s a
VUM.take Int
len MVector (PrimState m) cap
vecCap)
              Vector (Int, cap) -> ((Int, cap) -> m ()) -> m ()
forall (m :: * -> *) a b.
(Monad m, Unbox a) =>
Vector a -> (a -> m b) -> m ()
VU.forM_ Vector (Int, cap)
neighbors (((Int, cap) -> m ()) -> m ()) -> ((Int, cap) -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \(!Int
to, !cap
cap) -> do
                Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (cap
cap cap -> cap -> Bool
forall a. Eq a => a -> a -> Bool
/= cap
0) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
                  Int
levelTo <- MVector (PrimState m) Int -> Int -> m Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Int
level Int
to
                  Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
levelTo Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
                    Int
levelV <- MVector (PrimState m) Int -> Int -> m Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Int
level Int
v
                    MVector (PrimState m) Int -> Int -> Int -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Int
level Int
to (Int
levelV Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
                    -- FIXME: break on to == t
                    Queue (PrimState m) Int -> Int -> m ()
forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> a -> m ()
ACIQ.pushBack Queue (PrimState m) Int
que Int
to
              Int
levelT <- MVector (PrimState m) Int -> Int -> m Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Int
level Int
t
              Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
levelT Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== -Int
1) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
                m ()
loop

  MVector (PrimState m) Int
iter <- Int -> m (MVector (PrimState m) Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
nG
  let dfs :: Int -> cap -> m cap
dfs Int
v cap
up
        | Int
v Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
s = cap -> m cap
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure cap
up
        | Bool
otherwise = do
            Int
len <- GrowVec (PrimState m) (Int, Int, cap) -> m Int
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> m Int
ACIGV.length (Vector (GrowVec (PrimState m) (Int, Int, cap))
gG Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> GrowVec (PrimState m) (Int, Int, cap)
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
v)
            Int
levelV <- MVector (PrimState m) Int -> Int -> m Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Int
level Int
v
            cap
result <- (((cap -> m cap) -> cap -> m cap) -> cap -> m cap)
-> cap -> ((cap -> m cap) -> cap -> m cap) -> m cap
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((cap -> m cap) -> cap -> m cap) -> cap -> m cap
forall a. (a -> a) -> a
fix cap
0 (((cap -> m cap) -> cap -> m cap) -> m cap)
-> ((cap -> m cap) -> cap -> m cap) -> m cap
forall a b. (a -> b) -> a -> b
$ \cap -> m cap
loop cap
res -> do
              Int
i <- MVector (PrimState m) Int -> Int -> m Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Int
iter Int
v
              if Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
len
                then cap -> m cap
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure cap
res
                else do
                  MVector (PrimState m) Int -> Int -> Int -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Int
iter Int
v (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
                  (!Int
to, !Int
iRevEdge, !cap
_) <- GrowVec (PrimState m) (Int, Int, cap) -> Int -> m (Int, Int, cap)
forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> Int -> m a
ACIGV.read (Vector (GrowVec (PrimState m) (Int, Int, cap))
gG Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> GrowVec (PrimState m) (Int, Int, cap)
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
v) Int
i
                  Int
levelTo <- MVector (PrimState m) Int -> Int -> m Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Int
level Int
to
                  cap
revCap <- Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> Int -> m cap
forall (m :: * -> *) cap.
(HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) =>
Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> Int -> m cap
readCapacity Vector (GrowVec (PrimState m) (Int, Int, cap))
gG Int
to Int
iRevEdge
                  if Int
levelV Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
levelTo Bool -> Bool -> Bool
|| cap
revCap cap -> cap -> Bool
forall a. Eq a => a -> a -> Bool
== cap
0
                    then cap -> m cap
loop cap
res
                    else do
                      cap
d <- Int -> cap -> m cap
dfs Int
to (cap -> m cap) -> cap -> m cap
forall a b. (a -> b) -> a -> b
$! cap -> cap -> cap
forall a. Ord a => a -> a -> a
min (cap
up cap -> cap -> cap
forall a. Num a => a -> a -> a
- cap
res) cap
revCap
                      if cap
d cap -> cap -> Bool
forall a. Ord a => a -> a -> Bool
<= cap
0
                        then cap -> m cap
loop cap
res -- no flow. ignore
                        else do
                          GrowVec (PrimState m) (Int, Int, cap)
-> (cap -> cap) -> Int -> m ()
forall (m :: * -> *) cap.
(HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) =>
GrowVec (PrimState m) (Int, Int, cap)
-> (cap -> cap) -> Int -> m ()
modifyCapacity (Vector (GrowVec (PrimState m) (Int, Int, cap))
gG Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> GrowVec (PrimState m) (Int, Int, cap)
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
v) (cap -> cap -> cap
forall a. Num a => a -> a -> a
+ cap
d) Int
i
                          GrowVec (PrimState m) (Int, Int, cap)
-> (cap -> cap) -> Int -> m ()
forall (m :: * -> *) cap.
(HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) =>
GrowVec (PrimState m) (Int, Int, cap)
-> (cap -> cap) -> Int -> m ()
modifyCapacity (Vector (GrowVec (PrimState m) (Int, Int, cap))
gG Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> GrowVec (PrimState m) (Int, Int, cap)
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
to) (cap -> cap -> cap
forall a. Num a => a -> a -> a
subtract cap
d) Int
iRevEdge
                          let !res' :: cap
res' = cap
res cap -> cap -> cap
forall a. Num a => a -> a -> a
+ cap
d
                          if cap
res' cap -> cap -> Bool
forall a. Eq a => a -> a -> Bool
== cap
up
                            then cap -> m cap
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure cap
res'
                            else cap -> m cap
loop cap
res' -- next neighbor
            MVector (PrimState m) Int -> Int -> Int -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Int
level Int
v Int
nG
            cap -> m cap
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure cap
result

  (((cap -> m cap) -> cap -> m cap) -> cap -> m cap)
-> cap -> ((cap -> m cap) -> cap -> m cap) -> m cap
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((cap -> m cap) -> cap -> m cap) -> cap -> m cap
forall a. (a -> a) -> a
fix cap
0 (((cap -> m cap) -> cap -> m cap) -> m cap)
-> ((cap -> m cap) -> cap -> m cap) -> m cap
forall a b. (a -> b) -> a -> b
$ \cap -> m cap
loop cap
flow_ -> do
    if cap
flow_ cap -> cap -> Bool
forall a. Ord a => a -> a -> Bool
>= cap
flowLimit
      then cap -> m cap
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure cap
flow_
      else do
        m ()
bfs
        Int
levelT <- MVector (PrimState m) Int -> Int -> m Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Int
level Int
t
        if Int
levelT Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== -Int
1
          then cap -> m cap
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure cap
flow_
          else do
            MVector (PrimState m) Int -> Int -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> a -> m ()
VGM.set MVector (PrimState m) Int
iter (Int
0 :: Int)
            cap
f <- Int -> cap -> m cap
dfs Int
t (cap -> m cap) -> cap -> m cap
forall a b. (a -> b) -> a -> b
$! cap
flowLimit cap -> cap -> cap
forall a. Num a => a -> a -> a
- cap
flow_
            if cap
f cap -> cap -> Bool
forall a. Eq a => a -> a -> Bool
== cap
0
              then cap -> m cap
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure cap
flow_
              else cap -> m cap
loop (cap -> m cap) -> cap -> m cap
forall a b. (a -> b) -> a -> b
$! cap
flow_ cap -> cap -> cap
forall a. Num a => a -> a -> a
+ cap
f

-- | `flow` with no capacity limit.
--
-- ==== Constraints
-- - \(s \neq t\)
-- - \(0 \leq s, t \lt n\)
--
-- ==== Complexity
-- - \(O((n + m) \sqrt{m})\) (if all the capacities are \(1\)),
-- - \(O(n^2 m)\) (general), or
-- - \(O(F(n + m))\), where \(F\) is the returned value
--
-- @since 1.0.0.0
{-# INLINE maxFlow #-}
maxFlow ::
  (HasCallStack, PrimMonad m, Num cap, Ord cap, Bounded cap, VU.Unbox cap) =>
  -- | Graph
  MfGraph (PrimState m) cap ->
  -- | Source @s@
  Int ->
  -- | Sink @t@
  Int ->
  -- | Max flow
  m cap
maxFlow :: forall (m :: * -> *) cap.
(HasCallStack, PrimMonad m, Num cap, Ord cap, Bounded cap,
 Unbox cap) =>
MfGraph (PrimState m) cap -> Int -> Int -> m cap
maxFlow MfGraph (PrimState m) cap
graph Int
s Int
t = MfGraph (PrimState m) cap -> Int -> Int -> cap -> m cap
forall (m :: * -> *) cap.
(HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) =>
MfGraph (PrimState m) cap -> Int -> Int -> cap -> m cap
flow MfGraph (PrimState m) cap
graph Int
s Int
t cap
forall a. Bounded a => a
maxBound

-- | Returns a vector of length \(n\), such that the \(i\)-th element is `True` if and only if there
-- is a directed path from \(s\) to \(i\) in the residual network. The returned vector corresponds
-- to a \(s-t\) minimum cut after calling @'maxFlow' s t@.
--
-- ==== Complexity
-- - \(O(n + m)\), where \(m\) is the number of added edges.
--
-- @since 1.0.0.0
{-# INLINE minCut #-}
minCut ::
  (PrimMonad m, Num cap, Ord cap, VU.Unbox cap) =>
  -- | Graph
  MfGraph (PrimState m) cap ->
  -- | Source @s@
  Int ->
  -- | Minimum cut
  m (VU.Vector Bit)
minCut :: forall (m :: * -> *) cap.
(PrimMonad m, Num cap, Ord cap, Unbox cap) =>
MfGraph (PrimState m) cap -> Int -> m (Vector Bit)
minCut MfGraph {Int
Vector (GrowVec (PrimState m) (Int, Int, cap))
GrowVec (PrimState m) (Int, Int)
nG :: forall s cap. MfGraph s cap -> Int
gG :: forall s cap. MfGraph s cap -> Vector (GrowVec s (Int, Int, cap))
posG :: forall s cap. MfGraph s cap -> GrowVec s (Int, Int)
nG :: Int
gG :: Vector (GrowVec (PrimState m) (Int, Int, cap))
posG :: GrowVec (PrimState m) (Int, Int)
..} Int
s = do
  MVector (PrimState m) Bit
visited <- Int -> Bit -> m (MVector (PrimState m) Bit)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> a -> m (MVector (PrimState m) a)
VUM.replicate Int
nG (Bit -> m (MVector (PrimState m) Bit))
-> Bit -> m (MVector (PrimState m) Bit)
forall a b. (a -> b) -> a -> b
$ Bool -> Bit
Bit Bool
False
  Queue (PrimState m) Int
que <- Int -> m (Queue (PrimState m) Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (Queue (PrimState m) a)
ACIQ.new Int
nG -- we could use a growable queue here
  Queue (PrimState m) Int -> Int -> m ()
forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> a -> m ()
ACIQ.pushBack Queue (PrimState m) Int
que Int
s
  (m () -> m ()) -> m ()
forall a. (a -> a) -> a
fix ((m () -> m ()) -> m ()) -> (m () -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \m ()
loop -> do
    Maybe Int
p_ <- Queue (PrimState m) Int -> m (Maybe Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> m (Maybe a)
ACIQ.popFront Queue (PrimState m) Int
que
    case Maybe Int
p_ of
      Maybe Int
Nothing -> () -> m ()
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
      Just Int
p -> do
        MVector (PrimState m) Bit -> Int -> Bit -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Bit
visited Int
p (Bit -> m ()) -> Bit -> m ()
forall a b. (a -> b) -> a -> b
$ Bool -> Bit
Bit Bool
True
        Vector (Int, Int, cap)
es <- GrowVec (PrimState m) (Int, Int, cap) -> m (Vector (Int, Int, cap))
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> m (Vector a)
ACIGV.unsafeFreeze (Vector (GrowVec (PrimState m) (Int, Int, cap))
gG Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> GrowVec (PrimState m) (Int, Int, cap)
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
p)
        Vector (Int, Int, cap) -> ((Int, Int, cap) -> m ()) -> m ()
forall (m :: * -> *) a b.
(Monad m, Unbox a) =>
Vector a -> (a -> m b) -> m ()
VU.forM_ Vector (Int, Int, cap)
es (((Int, Int, cap) -> m ()) -> m ())
-> ((Int, Int, cap) -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \(!Int
to, !Int
_, !cap
cap) -> do
          Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (cap
cap cap -> cap -> Bool
forall a. Eq a => a -> a -> Bool
/= cap
0) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
            Bit Bool
b <- MVector (PrimState m) Bit -> Int -> Bit -> m Bit
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m a
VGM.exchange MVector (PrimState m) Bit
visited Int
to (Bit -> m Bit) -> Bit -> m Bit
forall a b. (a -> b) -> a -> b
$ Bool -> Bit
Bit Bool
True
            Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless Bool
b (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
              Queue (PrimState m) Int -> Int -> m ()
forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> a -> m ()
ACIQ.pushBack Queue (PrimState m) Int
que Int
to
        m ()
loop
  MVector (PrimState m) Bit -> m (Vector Bit)
forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> m (Vector a)
VU.unsafeFreeze MVector (PrimState m) Bit
visited

-- | \(O(1)\) Returns the current internal state of \(i\)-th edge: @(from, to, cap, flow)@. 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
{-# INLINE getEdge #-}
getEdge ::
  (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap) =>
  -- | Graph
  MfGraph (PrimState m) cap ->
  -- | Vertex
  Int ->
  -- | Tuple of @(from, to, cap, flow)@
  m (Int, Int, cap, cap)
getEdge :: forall (m :: * -> *) cap.
(HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) =>
MfGraph (PrimState m) cap -> Int -> m (Int, Int, cap, cap)
getEdge MfGraph {Int
Vector (GrowVec (PrimState m) (Int, Int, cap))
GrowVec (PrimState m) (Int, Int)
nG :: forall s cap. MfGraph s cap -> Int
gG :: forall s cap. MfGraph s cap -> Vector (GrowVec s (Int, Int, cap))
posG :: forall s cap. MfGraph s cap -> GrowVec s (Int, Int)
nG :: Int
gG :: Vector (GrowVec (PrimState m) (Int, Int, cap))
posG :: GrowVec (PrimState m) (Int, Int)
..} Int
i = do
  Int
m <- GrowVec (PrimState m) (Int, Int) -> m Int
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> m Int
ACIGV.length GrowVec (PrimState m) (Int, Int)
posG
  let !()
_ = HasCallStack => String -> Int -> Int -> ()
String -> Int -> Int -> ()
ACIA.checkEdge String
"AtCoder.MaxFlow.getEdge" Int
i Int
m
  (!Int
from, !Int
iEdge) <- GrowVec (PrimState m) (Int, Int) -> Int -> m (Int, Int)
forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> Int -> m a
ACIGV.read GrowVec (PrimState m) (Int, Int)
posG Int
i
  (!Int
to, !Int
iRevEdge, !cap
cap) <- GrowVec (PrimState m) (Int, Int, cap) -> Int -> m (Int, Int, cap)
forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> Int -> m a
ACIGV.read (Vector (GrowVec (PrimState m) (Int, Int, cap))
gG Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> GrowVec (PrimState m) (Int, Int, cap)
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
from) Int
iEdge
  cap
revCap <- Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> Int -> m cap
forall (m :: * -> *) cap.
(HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) =>
Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> Int -> m cap
readCapacity Vector (GrowVec (PrimState m) (Int, Int, cap))
gG Int
to Int
iRevEdge
  (Int, Int, cap, cap) -> m (Int, Int, cap, cap)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
from, Int
to, cap
cap cap -> cap -> cap
forall a. Num a => a -> a -> a
+ cap
revCap, cap
revCap)

-- | Returns the current internal state of the edges: @(from, to, cap, flow)@. 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
{-# INLINE edges #-}
edges ::
  (PrimMonad m, Num cap, Ord cap, VU.Unbox cap) =>
  -- | Graph
  MfGraph (PrimState m) cap ->
  -- | Vector of @(from, to, cap, flow)@
  m (VU.Vector (Int, Int, cap, cap))
edges :: forall (m :: * -> *) cap.
(PrimMonad m, Num cap, Ord cap, Unbox cap) =>
MfGraph (PrimState m) cap -> m (Vector (Int, Int, cap, cap))
edges g :: MfGraph (PrimState m) cap
g@MfGraph {GrowVec (PrimState m) (Int, Int)
posG :: forall s cap. MfGraph s cap -> GrowVec s (Int, Int)
posG :: GrowVec (PrimState m) (Int, Int)
posG} = do
  Int
len <- GrowVec (PrimState m) (Int, Int) -> m Int
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> m Int
ACIGV.length GrowVec (PrimState m) (Int, Int)
posG
  Int
-> (Int -> m (Int, Int, cap, cap))
-> m (Vector (Int, Int, cap, cap))
forall (m :: * -> *) a.
(Monad m, Unbox a) =>
Int -> (Int -> m a) -> m (Vector a)
VU.generateM Int
len (MfGraph (PrimState m) cap -> Int -> m (Int, Int, cap, cap)
forall (m :: * -> *) cap.
(HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) =>
MfGraph (PrimState m) cap -> Int -> m (Int, Int, cap, cap)
getEdge MfGraph (PrimState m) cap
g)

-- | \(O(1)\) Changes the capacity and the flow amount of the $i$-th edge to @newCap@ and
-- @newFlow@, respectively. It oes not change the capacity or the flow amount of other edges.
--
-- ==== Constraints
-- - \(0 \leq \mathrm{newflow} \leq \mathrm{newcap}\)
--
-- ==== Complexity
-- - \(O(1)\)
--
-- @since 1.0.0.0
{-# INLINE changeEdge #-}
changeEdge ::
  (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap) =>
  -- | Graph
  MfGraph (PrimState m) cap ->
  -- | Edge index
  Int ->
  -- | New capacity
  cap ->
  -- | New flow
  cap ->
  m ()
changeEdge :: forall (m :: * -> *) cap.
(HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) =>
MfGraph (PrimState m) cap -> Int -> cap -> cap -> m ()
changeEdge MfGraph {Int
Vector (GrowVec (PrimState m) (Int, Int, cap))
GrowVec (PrimState m) (Int, Int)
nG :: forall s cap. MfGraph s cap -> Int
gG :: forall s cap. MfGraph s cap -> Vector (GrowVec s (Int, Int, cap))
posG :: forall s cap. MfGraph s cap -> GrowVec s (Int, Int)
nG :: Int
gG :: Vector (GrowVec (PrimState m) (Int, Int, cap))
posG :: GrowVec (PrimState m) (Int, Int)
..} Int
i cap
newCap cap
newFlow = do
  Int
m <- GrowVec (PrimState m) (Int, Int) -> m Int
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> m Int
ACIGV.length GrowVec (PrimState m) (Int, Int)
posG
  let !()
_ = HasCallStack => String -> Int -> Int -> ()
String -> Int -> Int -> ()
ACIA.checkEdge String
"AtCoder.MaxFlow.changeEdge" Int
i Int
m
  let !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (cap
0 cap -> cap -> Bool
forall a. Ord a => a -> a -> Bool
<= cap
newFlow Bool -> Bool -> Bool
&& cap
newFlow cap -> cap -> Bool
forall a. Ord a => a -> a -> Bool
<= cap
newCap) String
"AtCoder.MaxFlow.changeEdge: invalid flow or capacity" -- not Show
  (!Int
from, !Int
iEdge) <- GrowVec (PrimState m) (Int, Int) -> Int -> m (Int, Int)
forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> Int -> m a
ACIGV.read GrowVec (PrimState m) (Int, Int)
posG Int
i
  (!Int
to, !Int
iRevEdge, !cap
_) <- GrowVec (PrimState m) (Int, Int, cap) -> Int -> m (Int, Int, cap)
forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
GrowVec (PrimState m) a -> Int -> m a
ACIGV.read (Vector (GrowVec (PrimState m) (Int, Int, cap))
gG Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> GrowVec (PrimState m) (Int, Int, cap)
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
from) Int
iEdge
  Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> Int -> cap -> m ()
forall (m :: * -> *) cap.
(HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) =>
Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> Int -> cap -> m ()
writeCapacity Vector (GrowVec (PrimState m) (Int, Int, cap))
gG Int
from Int
iEdge (cap -> m ()) -> cap -> m ()
forall a b. (a -> b) -> a -> b
$! cap
newCap cap -> cap -> cap
forall a. Num a => a -> a -> a
- cap
newFlow
  Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> Int -> cap -> m ()
forall (m :: * -> *) cap.
(HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) =>
Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> Int -> cap -> m ()
writeCapacity Vector (GrowVec (PrimState m) (Int, Int, cap))
gG Int
to Int
iRevEdge (cap -> m ()) -> cap -> m ()
forall a b. (a -> b) -> a -> b
$! cap
newFlow

-- | \(O(1)\) Internal helper.
{-# INLINE readCapacity #-}
readCapacity :: (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap) => V.Vector (ACIGV.GrowVec (PrimState m) (Int, Int, cap)) -> Int -> Int -> m cap
readCapacity :: forall (m :: * -> *) cap.
(HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) =>
Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> Int -> m cap
readCapacity Vector (GrowVec (PrimState m) (Int, Int, cap))
gvs Int
v Int
i = do
  (VUM.MV_3 Int
_ MVector (PrimState m) Int
_ MVector (PrimState m) Int
_ MVector (PrimState m) cap
c) <- MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap))
-> m (MVector (PrimState m) (Int, Int, cap))
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar (MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap))
 -> m (MVector (PrimState m) (Int, Int, cap)))
-> MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap))
-> m (MVector (PrimState m) (Int, Int, cap))
forall a b. (a -> b) -> a -> b
$ GrowVec (PrimState m) (Int, Int, cap)
-> MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap))
forall s a. GrowVec s a -> MutVar s (MVector s a)
ACIGV.vecGV (GrowVec (PrimState m) (Int, Int, cap)
 -> MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap)))
-> GrowVec (PrimState m) (Int, Int, cap)
-> MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap))
forall a b. (a -> b) -> a -> b
$ Vector (GrowVec (PrimState m) (Int, Int, cap))
gvs Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> GrowVec (PrimState m) (Int, Int, cap)
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
v
  MVector (PrimState m) cap -> Int -> m cap
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) cap
c Int
i

-- | \(O(1)\) Internal helper.
{-# INLINE writeCapacity #-}
writeCapacity :: (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap) => V.Vector (ACIGV.GrowVec (PrimState m) (Int, Int, cap)) -> Int -> Int -> cap -> m ()
writeCapacity :: forall (m :: * -> *) cap.
(HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) =>
Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> Int -> cap -> m ()
writeCapacity Vector (GrowVec (PrimState m) (Int, Int, cap))
gvs Int
v Int
i cap
cap = do
  (VUM.MV_3 Int
_ MVector (PrimState m) Int
_ MVector (PrimState m) Int
_ MVector (PrimState m) cap
c) <- MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap))
-> m (MVector (PrimState m) (Int, Int, cap))
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar (MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap))
 -> m (MVector (PrimState m) (Int, Int, cap)))
-> MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap))
-> m (MVector (PrimState m) (Int, Int, cap))
forall a b. (a -> b) -> a -> b
$ GrowVec (PrimState m) (Int, Int, cap)
-> MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap))
forall s a. GrowVec s a -> MutVar s (MVector s a)
ACIGV.vecGV (GrowVec (PrimState m) (Int, Int, cap)
 -> MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap)))
-> GrowVec (PrimState m) (Int, Int, cap)
-> MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap))
forall a b. (a -> b) -> a -> b
$ Vector (GrowVec (PrimState m) (Int, Int, cap))
gvs Vector (GrowVec (PrimState m) (Int, Int, cap))
-> Int -> GrowVec (PrimState m) (Int, Int, cap)
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
v
  MVector (PrimState m) cap -> Int -> cap -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) cap
c Int
i cap
cap

-- | \(O(1)\) Internal helper.
{-# INLINE modifyCapacity #-}
modifyCapacity :: (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap) => ACIGV.GrowVec (PrimState m) (Int, Int, cap) -> (cap -> cap) -> Int -> m ()
modifyCapacity :: forall (m :: * -> *) cap.
(HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) =>
GrowVec (PrimState m) (Int, Int, cap)
-> (cap -> cap) -> Int -> m ()
modifyCapacity GrowVec (PrimState m) (Int, Int, cap)
gv cap -> cap
f Int
i = do
  (VUM.MV_3 Int
_ MVector (PrimState m) Int
_ MVector (PrimState m) Int
_ MVector (PrimState m) cap
c) <- MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap))
-> m (MVector (PrimState m) (Int, Int, cap))
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar (MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap))
 -> m (MVector (PrimState m) (Int, Int, cap)))
-> MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap))
-> m (MVector (PrimState m) (Int, Int, cap))
forall a b. (a -> b) -> a -> b
$ GrowVec (PrimState m) (Int, Int, cap)
-> MutVar (PrimState m) (MVector (PrimState m) (Int, Int, cap))
forall s a. GrowVec s a -> MutVar s (MVector s a)
ACIGV.vecGV GrowVec (PrimState m) (Int, Int, cap)
gv
  MVector (PrimState m) cap -> (cap -> cap) -> Int -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> (a -> a) -> Int -> m ()
VUM.modify MVector (PrimState m) cap
c cap -> cap
f Int
i