埃德蒙兹-卡普算法

计算机科学中，埃德蒙兹-卡普算法（）通过实现福特-富尔克森算法来计算网络中的最大流，其时间复杂度为O(VE^2)。该算法由在1970年最先提出，并由和理查德·卡普在1972年独立发表。

C++實作
以下是关于埃德蒙兹-卡普算法的C++语言描述：
struct Main {
struct Edge {
int u, v, Capacity, Flow;

Edge (int u, int v, int Capacity, int Flow) :
u(u), v(v), Capacity(Capacity), Flow(Flow) {}
};

struct Edmonds_Karp {
vector Edges;
vector Graph[MAXN]; // 保存下标
int n, Augment[MAXN], Previous[MAXN];
// 当起点到 Augment[i] 的可改进量；

void Initialise(int n)
{
for (int i = 0; i Travel;
Travel.push(s);
Augment[s] = INT_MAX;

while (!Travel.empty()) {
int From = Travel.front();
Travel.pop();

for (int i = 0; i Temp.Flow) {
Previous[Temp.v] = Graph[From][i];
Augment[Temp.v] = min(Augment[From], Temp.Capacity - Temp.Flow);

Travel.push(Temp.v);
}
}

if (Augment[t]) break;
}

if (!Augment[t]) break;

for (int i = t; i != s; i = Edges[Previous[i]].From) {
Edges[Previous[i]].Flow += Augment[t];
Edges[Previous[i] ^ 1].Flow -= Augment[t];
}

FlowSum += Augment[t];
}

return flow;
}

Main(void) {}
};

参考资料
参见
*福特-富尔克森算法
*迪尼茨算法
*网络流