【概述】

FF 算法與 EK 算法是求解最大流的一般增廣路方法，其時(shí)間復(fù)雜度均為 O(n*m*m)

Ford-Fulkerson 算法是求解最大流的最基礎(chǔ)的算法，其核心思想是增廣路定理：網(wǎng)絡(luò)達(dá)到最大流當(dāng)且僅當(dāng)殘留網(wǎng)絡(luò)中沒(méi)有增廣路

程序的實(shí)現(xiàn)過(guò)程與增廣路求最大流的過(guò)程基本一致，即每一次更新都進(jìn)行一次找增廣路然后更新路徑上的流量的過(guò)程。

在傳統(tǒng)的 FF 算法中，利用 dfs?每次找增廣路的過(guò)程十分繁瑣，常常會(huì)走冤枉路，此時(shí)更新增廣路的復(fù)雜度就會(huì)增加，EK 算法為了規(guī)避這個(gè)問(wèn)題使用了 bfs 來(lái)尋找增廣路，然后在尋找增廣路的時(shí)候總是向離匯點(diǎn)越來(lái)越近的方向去尋找下一個(gè)結(jié)點(diǎn)。

【基本思想】

1）若存在增廣路徑，則找出一條增廣路徑（通過(guò) BFS）

2）沿著找出的增廣路徑進(jìn)行更新流量

3）當(dāng)沒(méi)有增廣路時(shí)，網(wǎng)絡(luò)達(dá)到最大流

【沿增廣路徑增廣方法】

第一步：計(jì)算可增加流量

? 設(shè)：某一增廣路徑結(jié)點(diǎn)為 a1,a2,...,an，可增加流的增加流量?dis=INF

? ? 若 (u,v) 是正向邊，則：dis=min(dis,c(ai,aj)-f(ai,aj))，其中：j=i+1,i=1,2,...,n-1

? ? 若 (u,v) 是逆向邊，則：dis=min(dis,f(ai,aj))，其中：j=i+1,i=1,2,...,n-1

第二步：更新流量

? 若 (u,v) 是正向邊，則：f(u,v)=f(u,v)+dis

? 若 (u,v) 是負(fù)向邊，則：f(u,v)=f(u,v)-dis（伴隨著這部分流量的減去，必有另一部分的管道流量會(huì)增加）

【模版】

1.FF 算法

struct Edge {int to, next;int cap; } edge[N * N]; int head[N], tot; bool vis[N], flag; LL res; void addEdge(int x, int y, int cap) {edge[tot].to = y;edge[tot].cap = cap;edge[tot].next = head[x];head[x] = tot++;edge[tot].to = x;edge[tot].cap = 0;edge[tot].next = head[y];head[y] = tot++; } int dfs(int x, int T, int flow) { // dfs求任意路徑if (x == T) {res += flow;flag = true;return flow;}vis[x] = true;for (int i = head[i]; i != -1; i = edge[i].next) {int x1 = edge[i].to;if (vis[x1] || edge[i].cap == 0)continue;int newFlow = dfs(x1, T, min(flow, edge[i].cap));if (flag) {edge[i].cap -= newFlow;edge[i ^ 1].cap += newFlow;return newFlow;}}return 0; } void FF(int S, int T) { //有增廣路就增廣flag = 0;memset(vis, 0, sizeof(vis));dfs(S, T, INF);while (flag) {flag = 0;memset(vis, 0, sizeof(vis));dfs(S, T, INF);} } int main() {memset(head, -1, sizeof(head));tot = 0;res = 0;int n, m;scanf("%d%d", &n, &m);for (int i = 1; i <= m; i++) {int x, y, cap;scanf("%d%d%d", &x, &y, &cap);addEdge(x, y, cap);}int S = 1, T = n;FF(S, T);printf("%d\n", res);return 0; }

2.EK 算法

int n, m; int cap[N][N]; //容量 int flow[N][N]; //流量int EK(int s, int t) { //沿著增廣路增廣int res = 0; //最大流int dis[N]; // a[i]表示從s到i的最小殘量int p[N]; //增廣路中的上一節(jié)點(diǎn)queue<int> Q;while (true) {memset(dis, 0, sizeof(dis));dis[s] = INF;Q.push(s);//計(jì)算可增加流量while (!Q.empty()) {int x = Q.front();Q.pop();for (int y = 1; y <= n; y++) {if (!dis[y] && cap[x][y] > flow[x][y]) {p[y] = x;Q.push(y);dis[y] = min(dis[x], cap[x][y] - flow[x][y]);}}}if (dis[t] == 0) //當(dāng)網(wǎng)絡(luò)中沒(méi)有增廣路徑break;//更新流量for (int x = t; x != s; x = p[x]) {flow[p[x]][x] += dis[t];flow[x][p[x]] -= dis[t];}res += dis[t];}return res; //返回最大流 }int main() {int n, m;scanf("%d%d", &n, &m);memset(cap, 0, sizeof(cap));memset(flow, 0, sizeof(flow));while (m--) {int x, y, w;scanf("%d%d%d", &x, &y, &w); //兩點(diǎn)的容量cap[x][y] = +w; //可能有重邊}printf("%d\n", EK(1, n));return 0; }

總結(jié)

以上是生活随笔為你收集整理的图论 —— 网络流 —— 最大流 —— FF 算法与 EK 算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。