运筹学最大流问题计算题：求解从起点到终点的最大流量

在一个有向图中，给定起点 s 和终点 t，以及每条边的容量（即最大流量），求从 s 到 t 的最大流量。

这是一个经典的运筹学问题，可以使用 Ford-Fulkerson 算法进行求解。该算法的核心思想是不断寻找从起点到终点的增广路径，并沿着该路径更新边的流量，直到无法找到增广路径为止。

以下是一个简单的例子：

给定以下有向图，其中 s 为起点，t 为终点，其他节点分别为 A、B、C、D：

     5        4
s -------> A -------> B ------> t
 \         | \       / |       /
  \        |  \     /  |      /
   \       |   \   /   |     /
    \      |    \ /    |    /
     \     |     X     |   /
      \    |    / \    |  /
       \   |   /   \   | /
        \  |  /     \  |/
         \ | /       \ |
          \|/         \|
           C ----------> D
             2        3

其中每条边的容量如下：

s 到 A 的边容量为 5
s 到 C 的边容量为 2
A 到 B 的边容量为 4
A 到 C 的边容量为 2
B 到 t 的边容量为 4
C 到 D 的边容量为 3
D 到 t 的边容量为 6

要求从 s 到 t 的最大流量，可以使用 Ford-Fulkerson 算法进行求解。其中，每次找到一条增广路径，并更新每条路径上的边的流量，直到无法找到增广路径为止。

以下是一个可能的求解过程：

初始时所有边的流量为 0，即

     0        0
s -------> A -------> B ------> t
 \         | \       / |       /
  \        |  \     /  |      /
   \       |   \   /   |     /
    \      |    \ /    |    /
     \     |     X     |   /
      \    |    / \    |  /
       \   |   /   \   | /
        \  |  /     \  |/
         \ | /       \ |
          \|/         \|
           C ----------> D
             0        0

使用 DFS 找到一条增广路径 s -> A -> C -> D -> t，该路径上的最小流量为 2。

     2        0
s -------> A -------> B ------> t
 \         | \       / |       /
  \        |  \     /  |      /
   \       |   \   /   |     /
    \      |    \ /    |    /
     \     |     X     |   /
      \    |    / \    |  /
       \   |   /   \   | /
        \  |  /     \  |/
         \ | /       \ |
          \|/         \|
           C ----------> D
             2        2

更新路径上的边的流量，即将 s 到 A 的边的流量增加 2，A 到 C 的边的流量减少 2，C 到 D 的边的流量增加 2，D 到 t 的边的流量增加 2。

     2        0
s -------> A -------> B ------> t
 \         | \       / |       /
  \        |  \     /  |      /
   \       |   \   /   |     /
    \      |    \ /    |    /
     \     |     X     |   /
      \    |    / \    |  /
       \   |   /   \   | /
        \  |  /     \  |/
         \ | /       \ |
          \|/         \|
           C ----------> D
             0        2

重复步骤 2 和 3，直到无法找到增广路径。此时，最大流量为 7。

     0        7
s -------> A -------> B ------> t
 \         | \       / |       /
  \        |  \     /  |      /
   \       |   \   /   |     /
    \      |    \ /    |    /
     \     |     X     |   /
      \    |    / \    |  /
       \   |   /   \   | /
        \  |  /     \  |/
         \ | /       \ |
          \|/         \|
           C ----------> D
             2        0

因此，从 s 到 t 的最大流量为 7。