最大流例題

最大流問題是一個在圖論中非常有名的問題，它的目標是在一個有向圖中找到一條流量最大的路徑。下面是一個簡單的例子：

給定一個有向圖，它的頂點分為源點 S 和匯點 T，以及一些中間頂點。每條邊都有一個容量，表示這條邊最多能通過的流量。最大流問題的目標是在不超過每條邊容量的前提下，從源點 S 到匯點 T 找到一條流量最大的路徑。

例如，給定以下這個有向圖：

S --(5)--> A --(2)--> B --(3)--> T
         |
         (1)--> C --(4)--> D --(2)--> T

在這個圖中，邊上的數字表示它的容量。我們要找到從 S 到 T 的最大流量。

解決這個問題可以使用福特-弗洛森算法（Ford-Fulkerson algorithm），這個算法通過不斷地找到增廣路徑（augmenting path）來增加流。

1. 初始時，所有的邊上的流量都是 0。
2. 找到一條從 S 到 T 的增廣路徑。增廣路徑是一條不經過 S 或 T 的中間頂點的路徑，並且每條邊的流量都沒有達到它的容量。
3. 沿著這條增廣路徑，將流量增加到邊的容量。
4. 重複步驟 2 和 3，直到找不到增廣路徑為止。

對於上面的例子，我們可以這樣找到最大流：

1. 初始時，所有邊的流量為 0。
2. 找到一條增廣路徑 S -> A -> B -> T，增加流量直到邊的容量為止。這時流量為 5（A 到 B 的邊達到容量，其餘邊未達到容量）。
3. 找不到增廣路徑，因為 S 到 T 的路徑上至少有一個邊已經達到容量。

所以，從 S 到 T 的最大流量為 5。

請注意，這個例子是一個非常簡單的情況，實際應用中可能會涉及到更大的圖和更複雜的算法。