什么是EK算法
EK (Edmond-Karp) 算法，说白了就是求最大流/费用流之类的问题的算法。什么是最大流
定义
带权的有向图$G=(V,E)$，满足以下条件，则称为网络流图$(flow network)$：- 仅有一个入度为$0$的顶点$s$，称$s$为源点。
- 仅有一个出度为$0$的顶点$t$，称$t$为汇点。
- 每条边的权值都为非负数，称为该边的容量，记作$c(i,j)$。
- 通过容量网络$G$中每条弧$< u,v>$上的实际流量(简称流量),记为$f(u,v)$，称为弧的流量。
例题
Luogu P3376 【模板】网络最大流题意
给出一个网络图，以及其源点和汇点，求出其网络最大流。思路
这是最大流的模板题，请往下阅读。增广路
增广路定义
增广路是指从源点$s$到汇点$t$的一条路，流过这条路，可以使得当前的流可以增加。如何求增广路
其实就是从源点$s$开始$bfs$即可，到达汇点$t$时，然后找到这个路径的权值的最小的边，然后把路径上的每一条边减去这个最小值即可。Code
寻找增广路
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
queue<int> q;//队列 bool bfs(){ while(!q.empty()) q.pop();//清空 memset(vis,0,sizeof(vis)); memset(pre,-1,sizeof(pre)); vis[s]=1;//源点标记 q.push(s);//入队 while(!q.empty()){ int u=q.front();q.pop(); for(int i=fir[u];i;i=nxt[i]){ int to=son[i]; if(vis[to]==0&&w[i]!=0){ pre[to].v=u; pre[to].edge=i;//记路径 if(to==t) return 1;//到达t点 vis[to]=1; q.push(to);//拓展 } } } return 0; } |
定义
|
1 2 3 4 5 |
int n,m,s,t,vis[MAXN]; int fir[MAXN],nxt[MAXN],w[MAXN],son[MAXN],tot=1,ans;//领接表 struct edge{ int v,edge;//用来记路径 }pre[101010]; |
EK算法核心（你别急，我还没说完）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int EK(){ ans=0; while(bfs()){ int Min=2e9; for(int i=t;i!=s;i=pre[i].v){ Min=min(Min,w[pre[i].edge]); } for(int i=t;i!=s;i=pre[i].v){ w[pre[i].edge]-=Min; } ans+=Min; } return ans; } |
反向边
为什么要建反边
然而$bfs$
然后每次$bfs$以后给相应的反边加上流量，正边减去流量。
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
int EK(){ ans=0; while(bfs()){ int Min=2e9; for(int i=t;i!=s;i=pre[i].v){ Min=min(Min,w[pre[i].edge]); } for(int i=t;i!=s;i=pre[i].v){ w[pre[i].edge]-=Min;//减去流量 w[pre[i].edge^1]+=Min;//加上流量 } ans+=Min; } return ans; } |
回归例题
所以这道最大流的模板题代码：Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
#include<algorithm> #include<bitset> #include<complex> #include<deque> #include<exception> #include<fstream> #include<functional> #include<iomanip> #include<ios> #include<iosfwd> #include<iostream> #include<istream> #include<iterator> #include<limits> #include<list> #include<locale> #include<map> #include<memory> #include<new> #include<numeric> #include<ostream> #include<queue> #include<set> #include<sstream> #include<stack> #include<stdexcept> #include<streambuf> #include<string> #include<typeinfo> #include<utility> #include<valarray> #include<vector> #include<cctype> #include<cerrno> #include<cfloat> #include<ciso646> #include<climits> #include<clocale> #include<cmath> #include<csetjmp> #include<csignal> #include<cstdarg> #include<cstddef> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> using namespace std; #define MAXN 200010 inline int read(){ int res=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar(); return res*f; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x<10) putchar(x+'0'); else{ write(x/10); putchar(x%10+'0'); } } //queue<int> q; //set<int> s; //priority_queue<int> q1; //priority_queue<int,vector<int>,greater<int> > q2; //list<int> l; //stack<int> s; int n,m,s,t,vis[MAXN]; int fir[MAXN],nxt[MAXN],w[MAXN],son[MAXN],tot=1,ans; struct edge{ int v,edge; }pre[101010]; void add(int x,int y,int z){ ++tot; nxt[tot]=fir[x]; fir[x]=tot; w[tot]=z; son[tot]=y; } queue<int> q; bool bfs(){ while(!q.empty()) q.pop(); memset(vis,0,sizeof(vis)); memset(pre,-1,sizeof(pre)); vis[s]=1; q.push(s); while(!q.empty()){ int u=q.front();q.pop(); for(int i=fir[u];i;i=nxt[i]){ int to=son[i]; if(vis[to]==0&&w[i]!=0){ pre[to].v=u; pre[to].edge=i; if(to==t) return 1; vis[to]=1; q.push(to); } } } return 0; } int EK(){ ans=0; while(bfs()){ int Min=2e9; for(int i=t;i!=s;i=pre[i].v){ Min=min(Min,w[pre[i].edge]); } for(int i=t;i!=s;i=pre[i].v){ w[pre[i].edge]-=Min; w[pre[i].edge^1]+=Min; } ans+=Min; } return ans; } int main(){ n=read();m=read();s=read();t=read(); for(int x,y,z,i=1;i<=m;i++){ x=read();y=read();z=read(); add(x,y,z); add(y,x,0); } write(EK());putchar('\n'); return 0; } |
EK算法拓展
费用流问题
Luogu P3381 【模板】最小费用最大流Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 |
#include<algorithm> #include<bitset> #include<complex> #include<deque> #include<exception> #include<fstream> #include<functional> #include<iomanip> #include<ios> #include<iosfwd> #include<iostream> #include<istream> #include<iterator> #include<limits> #include<list> #include<locale> #include<map> #include<memory> #include<new> #include<numeric> #include<ostream> #include<queue> #include<set> #include<sstream> #include<stack> #include<stdexcept> #include<streambuf> #include<string> #include<typeinfo> #include<utility> #include<valarray> #include<vector> #include<cctype> #include<cerrno> #include<cfloat> #include<ciso646> #include<climits> #include<clocale> #include<cmath> #include<csetjmp> #include<csignal> #include<cstdarg> #include<cstddef> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #define int long long using namespace std; #define MAXN 200010 inline int read(){ int res=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar(); return res*f; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x<10) putchar(x+'0'); else{ write(x/10); putchar(x%10+'0'); } } //queue<int> q; //set<int> s; //priority_queue<int> q1; //priority_queue<int,vector<int>,greater<int> > q2; //list<int> l; //stack<int> s; int n,m,s,t,vis[MAXN],dis[MAXN],anss; int fir[MAXN],nxt[MAXN],w[MAXN],son[MAXN],tot=1,ans,cost[MAXN]; struct edge{ int v,edge; }pre[101010]; void add(int x,int y,int z,int c){ ++tot; nxt[tot]=fir[x]; fir[x]=tot; w[tot]=z; son[tot]=y; cost[tot]=c; } queue<int> q; bool spfa(){ while(!q.empty()) q.pop(); memset(vis,0,sizeof(vis)); memset(pre,-1,sizeof(pre)); memset(dis,63,sizeof(dis)); dis[s]=0;dis[t]=2e9; vis[s]=1;q.push(s); while(!q.empty()){ int u=q.front();q.pop();vis[u]=0; for(int i=fir[u];i;i=nxt[i]){ int to=son[i]; if(w[i]>0&&dis[to]>dis[u]+cost[i]){ dis[to]=dis[u]+cost[i]; pre[to].edge=i; pre[to].v=u; if(vis[to]==0){ vis[to]=1; q.push(to); } } } } if(dis[t]<2e9) return 1; return 0; } int EK(){ ans=0;anss=0; while(spfa()){ int Min=2e9; for(int i=t;i!=s;i=pre[i].v){ Min=min(Min,w[pre[i].edge]); } for(int i=t;i!=s;i=pre[i].v){ w[pre[i].edge]-=Min; w[pre[i].edge^1]+=Min; } anss+=Min; ans+=Min*dis[t]; } return ans; } signed main(){ n=read();m=read();s=read();t=read(); for(int x,y,z,c,i=1;i<=m;i++){ x=read();y=read();z=read();c=read(); add(x,y,z,c); add(y,x,0,-c); } EK(); write(anss);putchar(' '); write(ans);putchar('\n'); return 0; } |
I will immediately seize your rss feed as I can’t to find your
e-mail subscription link or newsletter service.
Do you’ve any? Please permit me recognise in order that I could subscribe.
Thanks. http://www.epowersports.com/media/js/netsoltrademark.php?d=microscan.net%2F__media__%2Fjs%2Fnetsoltrademark.php%3Fd%3D918.network%2Fcasino-games%2F76-sky777