网络流dinic实现总结

太羞耻了,搞了半天居然没发现自己写的不是dinic,直到被一道时限紧的题目卡掉才发现

 int dfs(int now,int flow,int sum)
{
if(now==n) return flow;
for(int i=fir[now];i && (flow>sum);i=nex[i])
if(d[to[i]]==d[now]+ && flo[i])
zl=dfs(to[i],min(flow,flo[i]),),sum+=zl,flo[i]-=zl,flo[i^]+=zl;
if(sum==) d[now]=;
return sum;
}
bool bfs()
{
for(int i=;i<=n;i++) d[i]=;
for(h=,t=,l[]=,d[]=;h<=t;h++)
for(int i=fir[l[h]];i;i=nex[i])
if(!d[to[i]] && flo[i])
l[++t]=to[i],d[l[t]]=d[l[h]]+;
return d[n];
}

俗话说dinic=bfs+dfs,bfs和dfs各写9行真是和谐美妙啊

有几处地方保证了复杂度的优化:

1.在总流量达到限制时直接滚粗

2.如果从一个节点无法流到终点,那么就暂时无视这个点(直到重新标号)——一开始一直没写

在调用的时候可以直接写

 for(ans=;bfs();ans+=dfs(,INF,));

不要手贱在ans前面加int,又一次我搞半天都只能输出0,结果发现╮(╯▽╰)╭

——另外不是很理解网上把残余流量和流量分开写的方法,感觉有点冗余

未完待续

上一篇:NPOI导出Excel


下一篇:datatables隐藏列与createdRow渲染bootstrapSwitch形成的BUG