class FlowNetwork {
  private graph: number[][];
  private residualGraph: number[][];
  private vertices: number;

  constructor(vertices: number) {
    this.vertices = vertices;
    this.graph = Array.from({ length: vertices }, () => Array(vertices).fill(0));
    this.residualGraph = Array.from({ length: vertices }, () => Array(vertices).fill(0));
  }

  addEdge(from: number, to: number, capacity: number): void {
    this.graph[from][to] = capacity;
    this.residualGraph[from][to] = capacity;
    this.residualGraph[to][from] = 0;
  }

  fordFulkerson(source: number, sink: number): number {
    let maxFlow = 0;
    const parent = new Array(this.vertices).fill(-1);

    while (this.bfs(source, sink, parent)) {
      let pathFlow = Infinity;

      for (let v = sink; v !== source; v = parent[v]) {
        const u = parent[v];
        pathFlow = Math.min(pathFlow, this.residualGraph[u][v]);
      }

      for (let v = sink; v !== source; v = parent[v]) {
        const u = parent[v];
        this.residualGraph[u][v] -= pathFlow;
        this.residualGraph[v][u] += pathFlow;
      }

      maxFlow += pathFlow;
    }

    return maxFlow;
  }

  private bfs(source: number, sink: number, parent: number[]): boolean {
    const visited = new Array(this.vertices).fill(false);
    const queue: number[] = [];

    queue.push(source);
    visited[source] = true;
    parent[source] = -1;

    while (queue.length > 0) {
      const u = queue.shift()!;

      for (let v = 0; v < this.vertices; v += 1) {
        if (!visited[v] && this.residualGraph[u][v] > 0) {
          queue.push(v);
          parent[v] = u;
          visited[v] = true;
        }
      }
    }

    return visited[sink];
  }
}

function minCut(graph: number[][], source: number, sink: number): { cutValue: number; cut: [number, number][] } {
  const network = new FlowNetwork(graph.length);

  for (let i = 0; i < graph.length; i += 1) {
    for (let j = 0; j < graph[i].length; j += 1) {
      if (graph[i][j] > 0) {
        network.addEdge(i, j, graph[i][j]);
      }
    }
  }

  const maxFlow = network.fordFulkerson(source, sink);

  // 使用 BFS 找到可达顶点
  const visited = new Array(graph.length).fill(false);
  const queue: number[] = [];
  queue.push(source);
  visited[source] = true;

  while (queue.length > 0) {
    const u = queue.shift()!;

    for (let v = 0; v < graph.length; v += 1) {
      if (!visited[v] && network.getResidualCapacity(u, v) > 0) {
        queue.push(v);
        visited[v] = true;
      }
    }
  }

  // 找到割边
  const cut: [number, number][] = [];
  for (let i = 0; i < graph.length; i += 1) {
    for (let j = 0; j < graph.length; j += 1) {
      if (visited[i] && !visited[j] && graph[i][j] > 0) {
        cut.push([i, j]);
      }
    }
  }

  return { cutValue: maxFlow, cut };
}

// 为 FlowNetwork 添加获取残余容量的方法
declare module './flow-network' {
  interface FlowNetwork {
    getResidualCapacity(u: number, v: number): number;
  }
}

FlowNetwork.prototype.getResidualCapacity = function (u: number, v: number): number {
  return this.residualGraph[u][v];
};

function bipartiteMatching(graph: number[][]): number {
  const n = graph.length;
  const m = graph[0].length;
  const matchR = new Array(m).fill(-1);
  const seen = new Array(m).fill(false);

  let result = 0;

  for (let u = 0; u < n; u += 1) {
    seen.fill(false);
    if (bpm(graph, u, matchR, seen)) {
      result += 1;
    }
  }

  return result;
}

function bpm(graph: number[][], u: number, matchR: number[], seen: boolean[]): boolean {
  for (let v = 0; v < graph[u].length; v += 1) {
    if (graph[u][v] && !seen[v]) {
      seen[v] = true;

      if (matchR[v] < 0 || bpm(graph, matchR[v], matchR, seen)) {
        matchR[v] = u;
        return true;
      }
    }
  }

  return false;
}

interface Edge {
  to: number;
  capacity: number;
  cost: number;
  reverse: number;
}

class MinCostFlow {
  private graph: Edge[][][];
  private vertices: number;

  constructor(vertices: number) {
    this.vertices = vertices;
    this.graph = Array.from({ length: vertices }, () => []);
  }

  addEdge(from: number, to: number, capacity: number, cost: number): void {
    this.graph[from].push({
      to,
      capacity,
      cost,
      reverse: this.graph[to].length,
    });
    this.graph[to].push({
      to: from,
      capacity: 0,
      cost: -cost,
      reverse: this.graph[from].length - 1,
    });
  }

  minCostFlow(source: number, sink: number, flow: number): number {
    let totalCost = 0;
    const INF = Infinity;

    while (flow > 0) {
      const dist = new Array(this.vertices).fill(INF);
      const prevv = new Array(this.vertices).fill(0);
      const preve = new Array(this.vertices).fill(0);

      dist[source] = 0;

      // Bellman-Ford
      let update = true;
      while (update) {
        update = false;
        for (let v = 0; v < this.vertices; v += 1) {
          if (dist[v] === INF) continue;
          for (let i = 0; i < this.graph[v].length; i += 1) {
            const edge = this.graph[v][i];
            if (edge.capacity > 0 && dist[edge.to] > dist[v] + edge.cost) {
              dist[edge.to] = dist[v] + edge.cost;
              prevv[edge.to] = v;
              preve[edge.to] = i;
              update = true;
            }
          }
        }
      }

      if (dist[sink] === INF) break;

      let d = flow;
      for (let v = sink; v !== source; v = prevv[v]) {
        d = Math.min(d, this.graph[prevv[v]][preve[v]].capacity);
      }

      flow -= d;
      totalCost += d * dist[sink];

      for (let v = sink; v !== source; v = prevv[v]) {
        const edge = this.graph[prevv[v]][preve[v]];
        edge.capacity -= d;
        this.graph[v][edge.reverse].capacity += d;
      }
    }

    return totalCost;
  }
}