最大流ek算法和dinic算法总结
2021-06-07 12:03
标签:主函数 链表 www 额外 最大 复杂 最大流 algo mes
n为节点数量,m为边数量
EK算法复杂度:O(n*m^2)
dinic算法复杂度:O(n^2*m)
EK算法思想就是先用bfs找到一条增广路(从源点到汇点有流量的路),然后用pre数组记录这条路径上每一个节点的上一个节点。之后利用pre数组完成对这条路上所有边流量的消减,以及增加答案。看代码就清楚了,不复杂
例题:https://www.luogu.com.cn/problem/P3376
EK算法:
#include#include #include string.h> #include #include set> #include #include
EK算法另外一种
// #include//这个是链表版,这道题卡内存不能用链表 // #include// #include // #include // #include // #include // #include // #include // #define lson rt // #define rson rt // using namespace std; // typedef long long ll; // const int INF = 0x3f3f3f3f; // const int maxm = 20000 + 10; //边的数量 // const int maxn = 200+10; //点的数量 // struct Edge // { // int v, w,next; // } e[maxm]; // int cnt, n, m, st, en,head[maxn],dis[maxn]; // queue r; // inline void add_edge(int u,int v,int w){ // e[cnt].v=v; // e[cnt].w=w; // e[cnt].next=head[u]; // head[u]=cnt++; // e[cnt].v=u; // e[cnt].w=0; // e[cnt].next=head[v]; // head[v]=cnt++; // } // int bfs(){ // while(!r.empty()) r.pop(); // memset(dis,0,sizeof(dis)); // r.push(st); // dis[st]=1; // while(!r.empty()){ // int u=r.front(); // r.pop(); // for(int i=head[u];i!=-1;i=e[i].next){ // int v=e[i].v; // if(!dis[v] && e[i].w>0){ // dis[v]=dis[u]+1; // if(v==en) return 1; // r.push(v); // } // } // } // return 0; // } // int dfs(int u,int flow){ // if(u==en) return flow; // int k,tmp=flow; // for(int i=head[u];i!=-1;i=e[i].next){ // int v=e[i].v; // if(dis[v]==dis[u]+1 && e[i].w>0){ // k=dfs(v,min(tmp,e[i].w)); // if(!k) dis[v]=0; // tmp-=k;e[i].w-=k;e[i^1].w+=k; // if(!tmp) break; // } // } // return flow-tmp; // } // void init(){ // cnt=0; // memset(head,-1,sizeof(head)); // } // int main() // { // init(); // scanf("%d%d%d%d", &n, &m,&st,&en); // while (m--) // { // int u,v,w; // scanf("%d%d%d",&u,&v,&w); // add_edge(u,v,w); // } // int res=0; // while(bfs()){ // res+=dfs(st,INF); // } // printf("%d\n",res); // return 0; // } #include#include .h> #include#include string #include set > #include#include
dinic算法:
它就是利用bfs对图进行一个分层,然后通过dfs来增广.增广过程除了当前节点x外,还需要传入一个表示“目前为止所有边的最小残量”的limit,当前节点x为汇点或者limit==0时终止dfs过程,否则会多路增广。还有在dfs过程中的一个重要优化:保存每个节点x正在遍历的子边保存在cur[x]以免重复计算遍历过的子边.
cur数组原理是什么呢?其实就是当我们在对一个节点u(假设有多个儿子)进行增广时,把他的儿子1,2的可用流量都用完了,那么在下一次dfs模块走到u时,我们如果可以直接从儿子3开始进行增广就可以大大减少额外的时间开销
cur数组实现:我们可以在dfs里面做一点改动,即先定义一个cur数组,在dfs之前把邻接表的head数组拷贝到cur里面,然后在遍历u的时候同时把cur里面的边的下标后移,以达到将用完的边略去的目的
dinic算法:
#include#includestring.h> #include #include #include using namespace std; const int maxn=10000; const int INF=0x3f3f3f3f; int head[maxn],cnt,st,en,dis[maxn],cur[maxn]; struct edge { int v,next,c,flow; }e[maxn]; void add_edge(int x,int y,int z) { e[cnt].v=y; e[cnt].c=z; e[cnt].flow=0; e[cnt].next=head[x]; head[x]=cnt++; } bool bfs() { memset(dis,0,sizeof(dis)); dis[st]=1; queueint>r; r.push(st); while(!r.empty()) { int x=r.front(); r.pop(); for(int i=head[x];i!=-1;i=e[i].next) { int v=e[i].v; if(!dis[v] && e[i].c>e[i].flow) { dis[v]=dis[x]+1; r.push(v); } } } return dis[en]; } int dinic(int s,int limit) { if(s==en || !limit) return limit; int ans=0; for(int &i=cur[s];i!=-1;i=e[i].next) { int v=e[i].v,feed; if(dis[v]!=dis[s]+1) continue; feed=dinic(v,min(limit,e[i].c-e[i].flow)); if(feed) { e[i].flow+=feed; e[i^1].flow-=feed; limit-=feed; ans+=feed; if(limit==0) break; } } if(!ans) dis[s]=-1; return ans; } int main() { memset(head,-1,sizeof(head)); int n,f,d; scanf("%d%d%d",&n,&f,&d); st=0; en=2*n+f+d+1; for(int i=1;ii) { add_edge(st,2*n+i,1); add_edge(2*n+i,st,0); } for(int i=1;ii) { add_edge(2*n+f+i,en,1); add_edge(en,2*n+f+i,0); } for(int i=1;ii) { add_edge(i,n+i,1); add_edge(n+i,i,0); int sum1,sum2; scanf("%d%d",&sum1,&sum2); int x; for(int j=0;j j) { scanf("%d",&x); add_edge(x+2*n,i,1); add_edge(i,x+2*n,0); } for(int j=0;j j) { scanf("%d",&x); add_edge(n+i,x+f+2*n,1); add_edge(x+f+2*n,n+i,0); } }//主函数从开头到这就是建图 int ans=0; while(bfs()) { for(int i=0;i) cur[i]=head[i]; ans+=dinic(st,1); //这个1也可以改成无穷大 } printf("%d\n",ans); return 0; }
最大流ek算法和dinic算法总结
标签:主函数 链表 www 额外 最大 复杂 最大流 algo mes
原文地址:https://www.cnblogs.com/kongbursi-2292702937/p/14585252.html
上一篇:C语言实现顺序栈