最大流算法的Edmonds-Karp算法，實際用的不多因為復(fù)雜度比Dinic高，把流初始化為零流，Maxflow返回最大流的值，同時在算法結(jié)束時所有已標(biāo)號結(jié)點（a[u]>0的結(jié)點）構(gòu)成集合S，剩余結(jié)點構(gòu)成集合T，則（S,T）是圖的最小割

#include<bits/stdc++.h> using namespace std; const int maxn=10050; const int inf=2e9;struct Edge{int from,to,cap,flow;Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){} };struct EdmondsKarp{int n,m;vector<Edge> edges; //邊數(shù)的兩倍vector<int> g[maxn];//鄰接表，g[i][j]表示結(jié)點i的第j條邊在e數(shù)組中的序號int a[maxn]; //當(dāng)起點到i的可改進量int p[maxn]; //最短路樹上p的入弧編號void init(int n){this->n=n;for(int i=0;i<n;++i) g[i].clear();edges.clear();}void add(int from,int to,int cap){edges.push_back(Edge(from,to,cap,0));edges.push_back(Edge(to,from,0,0));m=edges.size();g[from].push_back(m-2);g[to].push_back(m-1);}int Maxflow(int s,int t){int flow=0;while(1){memset(a,0,sizeof(a));queue<int> que;que.push(s);a[s]=inf;while(!que.empty()){int x=que.front();que.pop();for(int i=0;i<g[x].size();++i){Edge& e=edges[g[x][i]];if(!a[e.to] && e.cap>e.flow){p[e.to]=g[x][i];a[e.to]=min(a[x],e.cap-e.flow);que.push(e.to);}}if(a[t]) break;}if(!a[t]) break;for(int u=t;u!=s;u=edges[p[u]].from){edges[p[u]].flow+=a[t];edges[p[u]^1].flow-=a[t];}flow+=a[t];}return flow;} };

轉(zhuǎn)載于:https://www.cnblogs.com/wafish/p/10465275.html

總結(jié)

以上是生活随笔為你收集整理的网络流最大流Edmonds-Karp算法（模板）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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