网络最大流算法—Dinic算法及优化

时间:2023-03-09 20:43:05
网络最大流算法—Dinic算法及优化

前置知识

网络最大流入门

前言

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+;
const int INF=1e8+;
inline char nc()
{
static char buf[MAXN],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
char c=nc();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=nc();}
while(c>=''&&c<=''){x=x*+c-'';c=nc();}
return x*f;
}
int N,M,S,T;
struct node
{
int v,flow,nxt;
}edge[MAXN*];
int head[MAXN],cur[MAXN],num=;//注意这里必须从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,,sizeof(deep));
deep[S]=;
int l=,r=;
q[++l]=S;
while(l<=r)
{
int p=q[l++];
for(int i=head[p];i!=-;i=edge[i].nxt)
if(!deep[edge[i].v]&&edge[i].flow)
{
deep[edge[i].v]=deep[p]+;q[++r]=edge[i].v;
if(edge[i].v==T) return ;//当找到汇点的时候直接返回 快30ms
}
}
return deep[T];
}
int DFS(int now,int nowflow)
{
if(now==T) return nowflow;
int totflow=;//从这个点总共可以增广多少流量
for(int i=head[now];i!=-;i=edge[i].nxt)//当前弧优化 快150ms
{
if(deep[edge[i].v]==deep[now]+&&edge[i].flow)//只有满足距离要求与流量要求的点才能进行增广
{
int canflow=DFS(edge[i].v,min(nowflow,edge[i].flow));
edge[i].flow-=canflow;edge[i^].flow+=canflow;//增广
totflow+=canflow;
nowflow-=canflow;
if(nowflow<=) break; //当前点已经没有流量 快100ms
}
}
return totflow;
}
void Dinic()
{
int ans=;
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,-,sizeof(head));
for(int i=;i<=M;i++)
{
int x,y,z;
x=read();y=read();z=read();
AddEdge(x,y,z);
}
Dinic();
return ;
}