最大流算法

最大流算法是一類用於解決網路流問題的算法，主要目的是在有向網路圖G=(V,E)中計算從源點s到匯點t的最大流量。這類算法可以分為兩大類：增廣路算法和預流推進算法。最大流的值等於源點到匯點的最小割容量，這意味著找到的最大流不會超過網路的容量限制。

在最大流問題中，剩餘容量cf(u,v)=c(u,v)−f(u,v)表示邊(u,v)的容量與已經通過的流量之差。如果存在一條從源節點s到目標節點t的路徑，且路徑上所有邊的剩餘容量都大於0，則這條路徑被稱為增廣路。殘量網路是由網路圖中所有節點和剩餘容量大於0的邊構成的子圖。

增廣路算法中，BFS（廣度優先搜尋）用於尋找增廣路，每次BFS配合一次增廣操作來增加流量。為了確保算法能夠找到最優解，每條有向邊都需要構造反向邊，因為當前增廣路可能不是最優的，後續增廣可能需要修改流量流向。

EK（Edmonds-Karp）算法是一種著名的最大流算法，其時間複雜度為O(nm^2)，其中n是節點數，m是邊數。EK算法通過構建殘量網路和增廣路徑來找到最大流。

以下是EK算法的一個簡單實現概述：

初始化前向星結構，包括邊數、節點的第一條邊的編號、節點標記數組等。

使用鏈式前向星結構存儲邊信息，包括邊的終點、同起點的下一條邊的編號、邊的流量。

初始化增廣路徑結構，包括邊的起點和邊的編號。

添加邊時，同時添加正向和反向兩條邊，以便於後續的增廣操作。

通過上述步驟，EK算法能夠有效地找到給定網路的最大流。