【网络流相关】最大流的Dinic算法实现
2012 年 2 月 18 日
于 \(EK\)
算法求最大流时每一次只求一条增广路,时间复杂度会比较高。尽管实际应用中表现比较优秀,但是有一些题目还是无法通过。
那么我们就会使用 \(Dinic\)
算法实现多路增广。
算法的基本流程如下:
-
\(BFS\)
对图进行分层,求出终点所在的层数 -
\(DFS\)
对每一条增广路的信息进行更新
仅仅这样看,虽然一次 \(BFS\)
能找到多条最短增广路,但是信息的更新仍然是逐条增广路进行更新,效率上并没有太大变化。
所以我们需要下面的两个优化:
-
记录起点到节点 \(P\)
的流 \(flow\)
和节点 \(P\)
到终点的流 \(used\)
。若 \(flow=used\)
,则不必再进行之后的 \(DFS\)
了,可以直接回溯。 -
使用一个 \(cur\)
数组复制链式前向星的 \(head\)
数组,在 \(DFS\)
时, \(cur\)
数组记录当前处理的边的编号。下次 \(DFS\)
到这个节点时,可以直接从 \(cur\)
数组记录的那条边开始。
第二个优化我们称之为 当前弧优化
。
原理:每一条已经处理完毕的边,必然不能再容纳下更多的流了。
\(Dinic\)
的时间复杂度是 \(O(n^2m)\)
。对于二分图匹配问题, \(Dinic\)
的时间复杂度是 \(O(m\sqrt n)\)
结合代码进行理解
#include#include using namespace std; int n,m,num,cnt,u,v,head[20005],cur[20005],dis[20005],ans; bool vis[20005]; struct data { int to,next,val; }e[5000005]; void add(int u,int v,int val) { e[++cnt].to=v; e[cnt].next=head[u]; head[u]=cnt; e[cnt].val=val; } bool bfs(int s,int t) { queue que; que.push(s); for (int i=1;i<=n;i++) dis[i]=0,vis[i]=false,cur[i]=head[i]; vis[s]=true; dis[s]=1; while (!que.empty()) { int now=que.front(); que.pop(); for (int i=head[now];i;i=e[i].next) { v=e[i].to; if (!vis[v]&&e[i].val>0) { dis[v]=dis[now]+1; vis[v]=true; if (v==t) return true; que.push(v); } } } return false; } int dfs(int now,int t,int flow) { if (!flow||now==t) return flow; int used=0; for (int i=cur[now];i;i=e[i].next) { cur[now]=i;//当前弧优化 v=e[i].to; if (dis[now]+1!=dis[v]) continue; int tmp=dfs(v,t,min(flow-used,e[i].val)); if (tmp) { e[i].val-=tmp; e[i^1].val+=tmp; used+=tmp; if (flow-used==0) return flow; } } return used; } void Dinic(int s,int t) { while (bfs(s,t)) ans+=dfs(s,t,0x7fffffff); } int main() { int s,t,w; scanf("%d%d%d%d",&n,&m,&s,&t); cnt=1; for (int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,0); } Dinic(s,t); printf("%d",ans); return 0; }