export function dinicsMaxFlow(
  n: number,
  source: number,
  sink: number,
  edges: number[][]
): number {
  if (n <= 0 || source < 0 || sink < 0 || source >= n || sink >= n) {
    return 0;
  }

  const m = edges.length;
  const maxEdges = m * 2;

  const head: number[] = new Array(n).fill(-1);
  const to: number[] = new Array(maxEdges).fill(0);
  const next: number[] = new Array(maxEdges).fill(0);
  const capacity: number[] = new Array(maxEdges).fill(0);
  const flow: number[] = new Array(maxEdges).fill(0);
  let edgeCount = 0;

  const addEdge = (u: number, v: number, cap: number): void => {
    // Arista directa (índice par: 0, 2, 4...)
    to[edgeCount] = v;
    capacity[edgeCount] = cap;
    flow[edgeCount] = 0;
    next[edgeCount] = head[u];
    head[u] = edgeCount++;

    // Arista residual (índice impar: 1, 3, 5...)
    to[edgeCount] = u;
    capacity[edgeCount] = 0;
    flow[edgeCount] = 0;
    next[edgeCount] = head[v];
    head[v] = edgeCount++;
  };

  for (let i = 0; i < m; i++) {
    addEdge(edges[i][0], edges[i][1], edges[i][2]);
  }

  const level: number[] = new Array(n).fill(-1);
  const ptr: number[] = new Array(n).fill(-1);

  const bfs = (): boolean => {
    level.fill(-1);
    level[source] = 0;

    const queue: number[] = [source];
    let headIdx = 0;

    while (headIdx < queue.length) {
      const u = queue[headIdx++];

      for (let e = head[u]; e !== -1; e = next[e]) {
        const v = to[e];
        if (capacity[e] - flow[e] > 0 && level[v] === -1) {
          level[v] = level[u] + 1;
          queue.push(v);
        }
      }
    }

    return level[sink] !== -1;
  };

  const dfs = (u: number, pushed: number): number => {
    if (pushed === 0 || u === sink) {
      return pushed;
    }

    for (let e = ptr[u]; e !== -1; e = next[e]) {
      ptr[u] = e;
      const v = to[e];

      if (level[u] + 1 !== level[v] || capacity[e] - flow[e] === 0) {
        continue;
      }

      const tr = dfs(v, Math.min(pushed, capacity[e] - flow[e]));
      if (tr === 0) {
        continue;
      }

      flow[e] += tr;
      flow[e ^ 1] -= tr;
      return tr;
    }

    return 0;
  };

  let maxFlow = 0;
  while (bfs()) {
    for (let i = 0; i < n; i++) {
      ptr[i] = head[i];
    }

    while (true) {
      const pushed = dfs(source, Infinity);
      if (pushed === 0) break;
      maxFlow += pushed;
    }
  }

  return maxFlow;
}