首页 > 代码库 > 网络流dinic实现总结
网络流dinic实现总结
太羞耻了，搞了半天居然没发现自己写的不是dinic，直到被一道时限紧的题目卡掉才发现
1 int dfs(int now,int flow,int sum) 2 { 3 if(now==n) return flow; 4 for(int i=fir[now];i && (flow>sum);i=nex[i]) 5 if(d[to[i]]==d[now]+1 && flo[i]) 6 zl=dfs(to[i],min(flow,flo[i]),0),sum+=zl,flo[i]-=zl,flo[i^1]+=zl; 7 if(sum==0) d[now]=0; 8 return sum; 9 }10 bool bfs()11 {12 for(int i=1;i<=n;i++) d[i]=0;13 for(h=1,t=1,l[1]=0,d[0]=1;h<=t;h++)14 for(int i=fir[l[h]];i;i=nex[i])15 if(!d[to[i]] && flo[i])16 l[++t]=to[i],d[l[t]]=d[l[h]]+1;17 return d[n];18 }
俗话说dinic=bfs+dfs，bfs和dfs各写9行真是和谐美妙啊
有几处地方保证了复杂度的优化：
1.在总流量达到限制时直接滚粗
2.如果从一个节点无法流到终点，那么就暂时无视这个点（直到重新标号）——一开始一直没写
在调用的时候可以直接写
1 for(ans=0;bfs();ans+=dfs(0,INF,0));
不要手贱在ans前面加int，又一次我搞半天都只能输出0，结果发现╮(╯▽╰)╭
——另外不是很理解网上把残余流量和流量分开写的方法，感觉有点冗余
未完待续
网络流dinic实现总结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。