FordFulkerson.scala

object FordFulkerson {
    val capacity = Array(
        Array(0, 1, 0),
        Array(0, 0, 2),
        Array(0, 0, 0)
    )

    def main(args: Array[String]): Unit = {
        println(maxFlow(0, 2))
        println(capacity.deep.mkString("\n"))
    }

    def maxFlow(s: Int, t: Int): Int = {
        var flow: Int = 0
        while (true) {
            val b = Array.fill(capacity.length)(false)
            val df: Int = findPath(b, s, t, Integer.MAX_VALUE)

            if (df == 0) {
                return flow
            }

            flow += df
        }

        0
    }

    def findPath(vis: Array[Boolean], u: Int, t: Int, f: Int): Int = {
        if (u == t) {
            return f
        }

        vis(u) = true
        for ((x, v) <- vis.view.zipWithIndex) {
            if (!x && capacity(u)(v) > 0) {
                val df = findPath(vis, v, t, Math.min(f, capacity(u)(v)))
                if (df > 0) {
                    capacity(u)(v) -= df
                    capacity(v)(u) += df
                    return df
                }
            }
        }

        0
    }
}