网络最大流算法—Dinic算法及优化
2018-06-17 21:21:40来源:未知 阅读 ()
前置知识
网络最大流入门
前言
Dinic在信息学奥赛中是一种最常用的求网络最大流的算法。
它凭借着思路直观,代码难度小,性能优越等优势,深受广大oier青睐
思想
$Dinic$算法属于增广路算法。
它的核心思想是:对于每一个点,对其所连的边进行增广,在增广的时候,每次增广“极大流”
这里有别于EK算法,EK算法是从边入手,而Dinic算法是从点入手
在增广的时候,对于一个点连出去的边都尝试进行增广,即多路增广
Dinic算法还引入了分层图这一概念,即对于$i$号节点,用$dis(i)$表示它到源点的距离,并规定,一条边能够被增广,当且仅当它连接的两个点$u,v$满足:$dis(v)=dis(u)+1$,这样可以大大优化其时间复杂度。
实现
有了上面的知识,Dinic实现起来也就比较简单了。
每次BFS构造分层图(注意必须每次都重新构造,因为每次增广之后会删除一些无用的边,也就会删除一些无用的点)
然后从源点开始多路增广
优化
- 当前弧优化:对于每个点,我们记录下它已经增广了哪些边,当再次回到这个点的时候,无视已经增广过的边,从下一条边开始增广
- 分层优化(自己xjb起的名字):在进行分层的时候,找到汇点立即退出
- 剩余量优化(也是自己起的):在进行增广的时候,如果该节点已经没有流量,直接退出
时间复杂度
Dinic算法的理论时间复杂度为$O(n^2*m)$
证明可以看这里
但是!
Dinic算法的性能在比赛中表现的非常优越。
按照集训队大佬ly的说法,我们可以认为Dinic算法的时间复杂度是线性的(比某标号算法不知道高到哪里去了)
代码
题目链接
#include<cstdio> #include<cstring> #include<queue> #define AddEdge(x,y,z) add_edge(x,y,z),add_edge(y,x,0); using namespace std; const int MAXN=1e6+1; const int INF=1e8+10; inline char nc() { static char buf[MAXN],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++; } inline int read() { char c=nc();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();} return x*f; } int N,M,S,T; struct node { int v,flow,nxt; }edge[MAXN*4]; int head[MAXN],cur[MAXN],num=0;//注意这里必须从0开始 inline void add_edge(int x,int y,int z) { edge[num].v=y; edge[num].flow=z; edge[num].nxt=head[x]; head[x]=num++; } int deep[MAXN],q[MAXN]; inline bool BFS() { memset(deep,0,sizeof(deep)); deep[S]=1; int l=0,r=1; q[++l]=S; while(l<=r) { int p=q[l++]; for(int i=head[p];i!=-1;i=edge[i].nxt) if(!deep[edge[i].v]&&edge[i].flow) { deep[edge[i].v]=deep[p]+1;q[++r]=edge[i].v; if(edge[i].v==T) return 1;//当找到汇点的时候直接返回 快30ms } } return deep[T]; } int DFS(int now,int nowflow) { if(now==T) return nowflow; int totflow=0;//从这个点总共可以增广多少流量 for(int i=head[now];i!=-1;i=edge[i].nxt)//当前弧优化 快150ms { if(deep[edge[i].v]==deep[now]+1&&edge[i].flow)//只有满足距离要求与流量要求的点才能进行增广 { int canflow=DFS(edge[i].v,min(nowflow,edge[i].flow)); edge[i].flow-=canflow;edge[i^1].flow+=canflow;//增广 totflow+=canflow; nowflow-=canflow; if(nowflow<=0) break; //当前点已经没有流量 快100ms } } return totflow; } void Dinic() { int ans=0; while(BFS())//每次构造分层图 { memcpy(cur,head,sizeof(head)); //当前弧优化 ans+=DFS(S,INF);//进行增广 } printf("%d",ans); } int main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif N=read();M=read();S=read();T=read(); memset(head,-1,sizeof(head)); for(int i=1;i<=M;i++) { int x,y,z; x=read();y=read();z=read(); AddEdge(x,y,z); } Dinic(); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:有符号类型与无符号类型值范围
- C++ rand函数 2020-06-10
- 一个工业级、跨平台、轻量级的 tcp 网络服务框架:gevent 2020-06-05
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 类欧几里得算法 2020-05-16
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash