網路流完全指南 — Ford-Fulkerson、Dinic 演算法與最大流最小割定理 | 資料結構與演算法

// Edmonds-Karp 演算法（Ford-Fulkerson + BFS）
// 時間複雜度：O(V × E²)
// 適用場景：中小規模圖，或作為理解網路流的入門

interface Edge {
  to: number;    // 終點
  cap: number;   // 當前殘餘容量
  rev: number;   // 反向邊在 graph[to] 中的索引
}

class EdmondsKarp {
  private graph: Edge[][]; // 鄰接表（含反向邊）
  private readonly n: number;

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

  // 添加有向邊（同時自動添加反向邊，反向邊初始容量 = 0）
  addEdge(from: number, to: number, cap: number): void {
    const forwardIdx = this.graph[to].length;    // 正向邊的反向邊索引
    const backwardIdx = this.graph[from].length;  // 反向邊的正向邊索引
    this.graph[from].push({ to, cap, rev: forwardIdx });
    this.graph[to].push({ to: from, cap: 0, rev: backwardIdx });
  }

  // BFS 尋找從 s 到 t 的最短增廣路徑
  // 返回路徑上的瓶頸容量（0 表示找不到路徑）
  private bfs(
    s: number,
    t: number,
    parent: Array<{ node: number; edgeIdx: number }>
  ): number {
    // parent[v] 記錄到達 v 的前一個節點和使用的邊索引
    parent.fill({ node: -1, edgeIdx: -1 });

    const visited = new Array(this.n).fill(false);
    visited[s] = true;
    const queue: Array<[number, number]> = [[s, Infinity]]; // [節點, 到此節點的瓶頸容量]
    let head = 0;

    while (head < queue.length) {
      const [u, flow] = queue[head++];

      for (let i = 0; i < this.graph[u].length; i++) {
        const e = this.graph[u][i];

        // 只走殘餘容量 > 0 且未被訪問的邊
        if (!visited[e.to] && e.cap > 0) {
          visited[e.to] = true;
          parent[e.to] = { node: u, edgeIdx: i };
          const newFlow = Math.min(flow, e.cap);

          if (e.to === t) return newFlow; // 到達匯點，返回瓶頸容量

          queue.push([e.to, newFlow]);
        }
      }
    }

    return 0; // 找不到增廣路徑
  }

  // 主函式：求 s 到 t 的最大流
  maxflow(s: number, t: number): number {
    let totalFlow = 0;
    const parent = new Array(this.n).fill({ node: -1, edgeIdx: -1 });

    let pathFlow: number;
    while ((pathFlow = this.bfs(s, t, parent)) > 0) {
      totalFlow += pathFlow;

      // 沿增廣路徑更新殘餘容量（回溯 parent 鏈）
      let curr = t;
      while (curr !== s) {
        const { node: prev, edgeIdx } = parent[curr];
        this.graph[prev][edgeIdx].cap -= pathFlow;                    // 正向邊容量減少
        this.graph[curr][this.graph[prev][edgeIdx].rev].cap += pathFlow; // 反向邊容量增加
        curr = prev;
      }
    }

    return totalFlow;
  }
}

// ─── 使用範例 ──────────────────────────────────────────────
const ek = new EdmondsKarp(6);

ek.addEdge(0, 1, 10); // s → 城市A，容量10
ek.addEdge(0, 2, 10); // s → 城市B，容量10
ek.addEdge(1, 3, 4);  // A → C，容量4
ek.addEdge(1, 2, 2);  // A → B，容量2
ek.addEdge(2, 4, 9);  // B → D，容量9
ek.addEdge(3, 5, 10); // C → t，容量10
ek.addEdge(4, 3, 6);  // D → C，容量6
ek.addEdge(4, 5, 10); // D → t，容量10

console.log("Edmonds-Karp 最大流:", ek.maxflow(0, 5)); // 輸出：19

// Dinic 最大流演算法
// 時間複雜度：O(V² × E)，單位容量圖為 O(E × √E)
// 適用場景：一般最大流問題，競賽中的主力演算法

interface DinicEdge {
  to: number;   // 終點
  cap: number;  // 當前殘餘容量
  rev: number;  // 反向邊在 graph[to] 中的索引（維護殘餘網路的關鍵）
}

class MaxFlow {
  private graph: DinicEdge[][]; // 鄰接表（含反向邊）
  private level: number[];     // BFS 分層，level[v] = s 到 v 的最短距離
  private iter: number[];      // 當前弧優化：避免重複遍歷飽和邊
  private readonly n: number;

  constructor(n: number) {
    this.n = n;
    this.graph = Array.from({ length: n }, () => []);
    this.level = new Array(n).fill(-1);
    this.iter = new Array(n).fill(0);
  }

  // 添加有向邊（同時添加殘餘反向邊，初始容量 = 0）
  addEdge(from: number, to: number, cap: number): void {
    const forwardIdx = this.graph[to].length;    // 正向邊的反向邊在 graph[to] 中的索引
    const backwardIdx = this.graph[from].length;  // 反向邊的正向邊在 graph[from] 中的索引
    this.graph[from].push({ to, cap, rev: forwardIdx });
    this.graph[to].push({ to: from, cap: 0, rev: backwardIdx }); // 反向邊，容量初始為 0
  }

  // BFS 建立分層圖：O(V + E)
  // 返回 true 表示 t 可達（還有增廣路徑）
  private bfs(s: number, t: number): boolean {
    this.level.fill(-1);
    const queue: number[] = [s];
    this.level[s] = 0;
    let head = 0;

    while (head < queue.length) {
      const v = queue[head++];
      for (const e of this.graph[v]) {
        // 只走殘餘容量 > 0 且未被訪問的邊
        if (e.cap > 0 && this.level[e.to] < 0) {
          this.level[e.to] = this.level[v] + 1;
          queue.push(e.to);
        }
      }
    }

    return this.level[t] >= 0; // 若 t 可達，返回 true
  }

  // DFS 找阻塞流（含當前弧優化）：O(V × E)
  // f = 從路徑上游傳來的可用流量上限
  private dfs(v: number, t: number, f: number): number {
    if (v === t) return f; // 到達匯點，返回可推流量

    // 當前弧優化：從上次停止的邊繼續掃描，跳過已飽和的邊
    for (; this.iter[v] < this.graph[v].length; this.iter[v]++) {
      const e = this.graph[v][this.iter[v]];

      // 只走分層圖中的邊（level[to] = level[v] + 1）且有殘餘容量
      if (e.cap > 0 && this.level[v] < this.level[e.to]) {
        const d = this.dfs(e.to, t, Math.min(f, e.cap));
        if (d > 0) {
          e.cap -= d;                          // 正向邊容量減少
          this.graph[e.to][e.rev].cap += d;    // 反向邊容量增加（允許「退流」）
          return d;
        }
      }
    }

    return 0; // 此節點已無法推流
  }

  // 主函式：求 s 到 t 的最大流
  // 每輪 BFS + DFS，最多 O(V) 輪
  maxflow(s: number, t: number): number {
    let flow = 0;

    while (this.bfs(s, t)) {
      // 每次 BFS 後重置當前弧指針
      this.iter.fill(0);

      let f: number;
      // 在當前分層圖上反覆推流，直到阻塞
      while ((f = this.dfs(s, t, Infinity)) > 0) {
        flow += f;
      }
    }

    return flow;
  }

  // 求最小割：在最大流計算完成後，BFS 仍可達的節點構成 S 集合
  minCut(s: number): boolean[] {
    const inS = new Array(this.n).fill(false);
    for (let i = 0; i < this.n; i++) {
      inS[i] = this.level[i] >= 0; // 最後一次 BFS 後可達的節點屬於 S
    }
    return inS;
  }

  // 輸出每條邊的實際流量（用於調試與分析）
  getEdgeFlows(): Array<{ from: number; to: number; flow: number; cap: number }> {
    const result: Array<{ from: number; to: number; flow: number; cap: number }> = [];
    for (let v = 0; v < this.n; v++) {
      for (const e of this.graph[v]) {
        // 正向邊的原始容量 = 當前殘餘容量 + 反向邊的殘餘容量
        const originalCap = e.cap + this.graph[e.to][e.rev].cap;
        if (originalCap > 0) {
          const flow = this.graph[e.to][e.rev].cap; // 反向邊容量 = 實際流量
          result.push({ from: v, to: e.to, flow, cap: originalCap });
        }
      }
    }
    return result;
  }
}

// ─── 使用範例：航線排程最大吞吐量 ──────────────────────────────
// 節點：s=0（出發地），t=5（目的地）
// 中轉站：1=城市A，2=城市B，3=城市C，4=城市D

const mf = new MaxFlow(6);

// 從源點出發的航線（容量 = 每日最大班次）
mf.addEdge(0, 1, 10); // s → 城市A，10班/天
mf.addEdge(0, 2, 10); // s → 城市B，10班/天

// 城市間連線
mf.addEdge(1, 3, 4);  // A → C，4班/天
mf.addEdge(1, 2, 2);  // A → B，2班/天（共用航線）
mf.addEdge(2, 4, 9);  // B → D，9班/天

// 到達目的地的航線
mf.addEdge(3, 5, 10); // C → t，10班/天
mf.addEdge(4, 3, 6);  // D → C，6班/天
mf.addEdge(4, 5, 10); // D → t，10班/天

console.log("Dinic 最大流:", mf.maxflow(0, 5)); // 輸出：19

// 輸出各邊實際流量
const flows = mf.getEdgeFlows();
flows.forEach(({ from, to, flow, cap }) => {
  if (flow > 0) console.log(`  ${from} → ${to}: ${flow}/${cap}`);
});

// 匈牙利演算法（Hungarian Algorithm）
// 時間複雜度：O(V × E)
// 適用：二分圖最大匹配（任務分配、人員調度）

class BipartiteMatching {
  private readonly leftN: number;  // 左側節點數量
  private readonly rightN: number; // 右側節點數量
  private adj: number[][];         // adj[左節點] = [可匹配的右節點列表]
  private matchL: number[];        // matchL[左節點] = 匹配的右節點（-1 表示未匹配）
  private matchR: number[];        // matchR[右節點] = 匹配的左節點（-1 表示未匹配）

  constructor(leftN: number, rightN: number) {
    this.leftN = leftN;
    this.rightN = rightN;
    this.adj = Array.from({ length: leftN }, () => []);
    this.matchL = new Array(leftN).fill(-1);
    this.matchR = new Array(rightN).fill(-1);
  }

  // 添加左節點 u 到右節點 v 的邊
  addEdge(u: number, v: number): void {
    this.adj[u].push(v);
  }

  // 對左節點 u 做 DFS，嘗試找增廣路徑
  // visited：本輪 DFS 中已訪問的右節點（避免循環）
  private dfs(u: number, visited: boolean[]): boolean {
    for (const v of this.adj[u]) {
      if (!visited[v]) {
        visited[v] = true; // 標記 v 在本輪已嘗試

        // 若 v 未匹配，或 v 的當前匹配左節點能改配其他右節點（增廣路徑）
        if (this.matchR[v] === -1 || this.dfs(this.matchR[v], visited)) {
          // 更新匹配：u 與 v 互相匹配
          this.matchL[u] = v;
          this.matchR[v] = u;
          return true; // 增廣成功
        }
      }
    }
    return false; // 無法增廣
  }

  // 執行最大匹配，返回匹配數量
  maxMatching(): number {
    let result = 0;

    for (let u = 0; u < this.leftN; u++) {
      // 每個左節點嘗試一次增廣，visited 每輪重置
      const visited = new Array(this.rightN).fill(false);
      if (this.dfs(u, visited)) {
        result++;
      }
    }

    return result;
  }

  // 獲取最終匹配對（左節點 → 右節點）
  getMatching(): Array<[number, number]> {
    const pairs: Array<[number, number]> = [];
    for (let u = 0; u < this.leftN; u++) {
      if (this.matchL[u] !== -1) {
        pairs.push([u, this.matchL[u]]);
      }
    }
    return pairs;
  }
}

// ─── 使用範例：工程師任務分配 ──────────────────────────────
// 場景：3 位工程師（左側）匹配 4 個任務（右側）
// 每位工程師有能力完成的任務集合

const bm = new BipartiteMatching(3, 4);

// 工程師 0：能完成任務 0 和任務 1
bm.addEdge(0, 0);
bm.addEdge(0, 1);

// 工程師 1：能完成任務 1 和任務 2
bm.addEdge(1, 1);
bm.addEdge(1, 2);

// 工程師 2：能完成任務 2 和任務 3
bm.addEdge(2, 2);
bm.addEdge(2, 3);

const matchCount = bm.maxMatching();
console.log(`最大匹配數（同時完成的任務數）: ${matchCount}`); // 輸出：3

const pairs = bm.getMatching();
pairs.forEach(([eng, task]) => {
  console.log(`  工程師${eng} → 任務${task}`);
});
// 工程師0 → 任務0（或任務1）
// 工程師1 → 任務1（或任務2）
// 工程師2 → 任務2（或任務3）

#include <bits/stdc++.h>
using namespace std;

// ===== Dinic 最大流演算法 =====
// 時間複雜度：O(V² × E)
// 對於單位容量圖（二分圖匹配）：O(E × √E)

struct Edge {
    int to, rev;  // 終點，反向邊索引
    int cap;      // 殘餘容量
};

class MaxFlow {
private:
    int n;
    vector<vector<Edge>> graph;
    vector<int> level; // BFS 分層
    vector<int> iter;  // 當前弧優化

    // BFS 建立分層圖
    bool bfs(int s, int t) {
        level.assign(n, -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);

        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (const auto& e : graph[v]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }

        return level[t] >= 0;
    }

    // DFS 推阻塞流（含當前弧優化）
    // 注意 int& i = iter[v] 是 C++ 引用，直接修改 iter[v] 的值
    int dfs(int v, int t, int f) {
        if (v == t) return f;

        for (int& i = iter[v]; i < (int)graph[v].size(); i++) {
            Edge& e = graph[v][i];

            if (e.cap > 0 && level[v] < level[e.to]) {
                int d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    graph[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }

        return 0;
    }

public:
    explicit MaxFlow(int n) : n(n), graph(n), level(n), iter(n) {}

    // 添加有向邊（自動添加反向邊）
    void addEdge(int from, int to, int cap) {
        int fwdIdx = graph[to].size();
        int bwdIdx = graph[from].size();
        graph[from].push_back({ to, fwdIdx, cap });
        graph[to].push_back({ from, bwdIdx, 0 }); // 反向邊初始容量 0
    }

    // 求最大流
    int maxflow(int s, int t) {
        int flow = 0;

        while (bfs(s, t)) {
            iter.assign(n, 0);
            int f;
            while ((f = dfs(s, t, INT_MAX)) > 0) {
                flow += f;
            }
        }

        return flow;
    }

    // 找最小割的 S 集合（BFS 後 level[v] >= 0 的節點）
    vector<bool> minCutS(int s, int t) {
        maxflow(s, t); // 先求最大流
        bfs(s, t);     // 最後一次 BFS 確定可達節點
        vector<bool> inS(n);
        for (int i = 0; i < n; i++) {
            inS[i] = (level[i] >= 0); // 可達 = 在 S 集合中
        }
        return inS;
    }
};

// ===== 匈牙利演算法（二部圖最大匹配）=====

class BipartiteMatching {
private:
    int leftN, rightN;
    vector<vector<int>> adj;
    vector<int> matchR; // matchR[右節點] = 匹配的左節點

    bool dfs(int u, vector<bool>& visited) {
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                if (matchR[v] == -1 || dfs(matchR[v], visited)) {
                    matchR[v] = u;
                    return true;
                }
            }
        }
        return false;
    }

public:
    BipartiteMatching(int leftN, int rightN)
        : leftN(leftN), rightN(rightN),
          adj(leftN), matchR(rightN, -1) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    int maxMatching() {
        int result = 0;
        for (int u = 0; u < leftN; u++) {
            vector<bool> visited(rightN, false);
            if (dfs(u, visited)) result++;
        }
        return result;
    }

    // 輸出最終匹配對
    void printMatching() const {
        for (int v = 0; v < rightN; v++) {
            if (matchR[v] != -1) {
                cout << "左" << matchR[v] << " <-> 右" << v << "\n";
            }
        }
    }
};

// ===== 主程式：測試 =====

int main() {
    // 測試 Dinic 最大流
    {
        MaxFlow mf(6);
        mf.addEdge(0, 1, 10);
        mf.addEdge(0, 2, 10);
        mf.addEdge(1, 3, 4);
        mf.addEdge(1, 2, 2);
        mf.addEdge(2, 4, 9);
        mf.addEdge(3, 5, 10);
        mf.addEdge(4, 3, 6);
        mf.addEdge(4, 5, 10);

        cout << "最大流: " << mf.maxflow(0, 5) << "\n"; // 19
    }

    // 測試二部圖匹配
    {
        BipartiteMatching bm(3, 4);
        bm.addEdge(0, 0); bm.addEdge(0, 1);
        bm.addEdge(1, 1); bm.addEdge(1, 2);
        bm.addEdge(2, 2); bm.addEdge(2, 3);

        cout << "最大匹配: " << bm.maxMatching() << "\n"; // 3
        bm.printMatching();
    }

    return 0;
}

// 陷阱 1：忘記添加反向邊
// 錯誤：只有正向邊，殘餘網路不完整，演算法無法退流
graph[from].push({ to, cap, rev: 0 }); // 沒有反向邊！

// 正確：同時添加反向邊（容量為 0）
graph[from].push({ to, cap, rev: graph[to].length });
graph[to].push({ to: from, cap: 0, rev: graph[from].length - 1 });

// 陷阱 2：Dinic 遺漏當前弧優化
// 錯誤：每次 DFS 都從第 0 條邊開始，退化為 O(V × E²)
for (const e of graph[v]) { /* 每次都掃描所有邊 */ }

// 正確：用 iter[v] 持續前進
for (; iter[v] < graph[v].length; iter[v]++) { /* 跳過已飽和邊 */ }

// 陷阱 3：匈牙利演算法的 visited 沒有每輪重置
// 錯誤：visited 跨輪持久，導致右側節點被錯誤鎖定
const visited = new Array(rightN).fill(false); // 在迴圈外宣告
for (let u = 0; u < leftN; u++) {
  dfs(u, visited); // 前一輪的 visited 影響後一輪！
}

// 正確：每個左節點嘗試前重置 visited
for (let u = 0; u < leftN; u++) {
  const visited = new Array(rightN).fill(false); // 每輪重新建立
  dfs(u, visited);
}

// BFS 染色法：O(V + E)
// 二分圖的充要條件：不存在奇數長度的環
function isBipartite(graph: number[][]): boolean {
  const n = graph.length;
  const color = new Array(n).fill(-1); // -1 表示未染色

  for (let start = 0; start < n; start++) {
    if (color[start] !== -1) continue; // 已染色，跳過

    // BFS 染色
    const queue: number[] = [start];
    color[start] = 0;
    let head = 0;

    while (head < queue.length) {
      const u = queue[head++];
      for (const v of graph[u]) {
        if (color[v] === -1) {
          color[v] = 1 - color[u]; // 鄰居染相反顏色
          queue.push(v);
        } else if (color[v] === color[u]) {
          return false; // 相鄰節點同色，不是二分圖
        }
      }
    }
  }

  return true;
  // 時間複雜度：O(V + E)；空間複雜度：O(V)
}

// 提示：將座位按 (row + col) % 2 分為兩組
// 建立二分圖：有作弊風險的座位對之間連邊
// 最大可坐學生數 = 可用座位數 - 最大匹配數（Konig 定理）
// 實作時直接用匈牙利演算法求最大匹配

function maxStudents(seats: string[][]): number {
  const m = seats.length, n = seats[0].length;
  const dirs = [[-1, -1], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 1]];

  // 將座位編號，分為左右兩組
  let available = 0;
  const id = Array.from({ length: m }, () => new Array(n).fill(-1));
  const leftNodes: number[][] = []; // (row+col) % 2 === 0 的座位
  const rightNodes: number[][] = []; // (row+col) % 2 === 1 的座位

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (seats[i][j] === '.') {
        available++;
        if ((i + j) % 2 === 0) {
          id[i][j] = leftNodes.length;
          leftNodes.push([i, j]);
        } else {
          id[i][j] = rightNodes.length;
          rightNodes.push([i, j]);
        }
      }
    }
  }

  // 建立二分圖匹配
  const bm = new BipartiteMatching(leftNodes.length, rightNodes.length);
  for (const [r, c] of leftNodes) {
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < m && nc >= 0 && nc < n && id[nr][nc] !== -1 && (nr + nc) % 2 === 1) {
        bm.addEdge(id[r][c], id[nr][nc]);
      }
    }
  }

  // Konig 定理：最大獨立集 = 總數 - 最大匹配
  return available - bm.maxMatching();
}