Island Transport (无向图Dinic算法+当前弧优化)
读题
给定一个无向图,求从最左侧的点到最右侧的点的最大流。
解题
无向图的最大流与有向图的最大流的区别在于反向边的流量不是零而是与正向边相等。注意这点之后,再打一个Dinic算法模板。考虑到数据特别地大,需要进行当前弧优化。即在每一次找增广路前进行:
while(bfs())
{
for(int i=1;i<=N;i++)
cur[i]=head[i];
ans+=dfs(S,INF);
}
并且在dfs中,及将i=head[u]改成:
for(int &i=cur[u];i!=-1;i=e[i].next)
AC代码
//8923ms 15MB
#include
#include
#include
#include
#include