A typescript implementation of the MCMF (Min Cost Max Flow) algorithm.

The MCMF algorithm is an algorithm for solving network flow problems.

Install

• npm

  npm install --save @algorithm.ts/mcmf

• yarn

  yarn add @algorithm.ts/mcmf

Usage

• Codeforces contest 0277 Problem E (https://codeforces.com/contest/277/problem/E):

  import { Mcmf } from '@algorithm.ts/mcmf'
  
  const mcmf = new Mcmf()
  export function solveCodeforces0277E(coordinates: Array<[x: number, y: number]>): number {
    const N: number = coordinates.length
  
    const vertexes: IVertex[] = coordinates
      .map(([x, y]) => ({ x, y }))
      .sort((p, q) => {
        if (p.y === q.y) return p.x - q.x
        return q.y - p.y
      })
  
    const source = 0
    const target: number = N * 2 + 1
    mcmf.init(source, target, N * 2 + 2)
  
    for (let i = 0; i < N; ++i) {
      mcmf.addEdge(source, i + 1, 2, 0)
      mcmf.addEdge(N + i + 1, target, 1, 0)
      for (let j = i + 1; j < N; ++j) {
        if (vertexes[i].y === vertexes[j].y) continue
        mcmf.addEdge(i + 1, N + j + 1, 1, dist(vertexes[i], vertexes[j]))
      }
    }
  
    const { mincost, maxflow } = mcmf.minCostMaxFlow()
    const answer = maxflow === N - 1 ? mincost : -1
    return answer
  }
  
  function dist(p: IVertex, q: IVertex): number {
    const d = (p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y)
    return Math.sqrt(d)
  }
  
  interface IVertex {
    x: number
    y: number
  }

• A solution for Codeforces contest 1082 Problem G (https://codeforces.com/contest/1082/problem/G):

  import { Mcmf } from '@algorithm.ts/mcmf'
  
  const mcmf = new Mcmf()
  export function solveCodeforces1082G(
    nodes: number[],
    edges: Array<[u: number, v: number, weight: number]>,
  ): number {
    const n: number = nodes.length
    const m: number = edges.length
  
    const source = 0
    const target: number = n + m + 1
    mcmf.init(source, target, n + m + 2)
  
    for (let i = 0; i < n; ++i) {
      const weight: number = nodes[i]
      mcmf.addEdge(i + 1, target, weight, 0)
    }
  
    let answer = 0
    for (let i = 0; i < m; ++i) {
      const [u, v, weight] = edges[i]
      const x = n + i
      answer += weight
      mcmf.addEdge(source, x, weight, 0)
      mcmf.addEdge(x, u, Number.MAX_SAFE_INTEGER, 0)
      mcmf.addEdge(x, v, Number.MAX_SAFE_INTEGER, 0)
    }
  
    const { mincost, maxflow } = mcmf.minCostMaxFlow()
    answer -= maxflow
    return answer
  }

• A solution for leetcode "Maximum Students Taking Exam" (https://leetcode.com/problems/maximum-students-taking-exam/):

  import { Mcmf } from '@algorithm.ts/mcmf'
  
  export function maxStudents(seats: string[][]): number {
    const R: number = seats.length
    if (R <= 0) return 0
  
    const C: number = seats[0].length
    if (C <= 0) return 0
  
    let total = 0
    const seatCodes: number[][] = new Array(R)
    for (let r = 0; r < R; ++r) seatCodes[r] = new Array(C).fill(-1)
  
    for (let r = 0; r < R; ++r) {
      for (let c = 0; c < C; ++c) {
        if (seats[r][c] === '.') seatCodes[r][c] = total++
      }
    }
  
    if (total <= 0) return 0
    if (total === 1) return 1
  
    const source: number = total * 2
    const target: number = source + 1
    const mcmf = new Mcmf()
    mcmf.init(source, target, target + 1)
  
    for (let r = 0; r < R; ++r) {
      for (let c = 0; c < C; ++c) {
        const u: number = seatCodes[r][c]
        if (u > -1) {
          mcmf.addEdge(source, u, 1, 0)
          mcmf.addEdge(u + total, target, 1, 0)
          if (r > 0) {
            // Check upper left
            if (c > 0 && seatCodes[r - 1][c - 1] > -1) {
              const v: number = seatCodes[r - 1][c - 1]
              mcmf.addEdge(u, v + total, 1, 0)
              mcmf.addEdge(v, u + total, 1, 0)
            }
  
            // Check upper right
            if (c + 1 < C && seatCodes[r - 1][c + 1] > -1) {
              const v: number = seatCodes[r - 1][c + 1]
              mcmf.addEdge(u, v + total, 1, 0)
              mcmf.addEdge(v, u + total, 1, 0)
            }
          }
  
          // Check left
          if (c > 0 && seatCodes[r][c - 1] > -1) {
            const v: number = seatCodes[r][c - 1]
            mcmf.addEdge(u, v + total, 1, 0)
            mcmf.addEdge(v, u + total, 1, 0)
          }
        }
      }
    }
  
    const { mincost, maxflow } = mcmf.minCostMaxFlow()
    const totalPaired: number = maxflow / 2
    return total - totalPaired
  }

Related

• @algorithm.ts/dinic
• @algorithm.ts/mcmf
• 网络流 24 题
• 网络流基础之最大权闭合图