一、概述
Dinic算法是最大流算法中的一种，其时间复杂度为O(n^2*m)，但是有更好的最坏时间复杂度O(nm*log(U))，与Hopcroft−Karp的O(m^2*n^0.5)相比，在密集图或者容量较大时，Dinic算法对于求解最大流有更好的表现，适用性更广。
二、原理
Dinic算法的基本思路是：通过多次增广，每次增加的流量不低于上一次增加的流量，直至无法增广为止，这样求得的就是最大流量。
具体思路如下：
1.首先设置dfs流程，使其能够和BFS流程相对应，dfs的返回值代表可以从当前节点流入汇点的最大流量，如果当前节点等于源点就返回无穷大（因为一开始源点的可行流量等于无穷）
2.其次，设置BFS流程，使其在调用dfs时可以从当前节点到达汇点（即dist[t]!=-1），并返回增加的流量，如果增加的流量为0或者小于0，则直接break（即优化掉死路）
3.最后通过不停的调用BFS和DFS，每次维护一组残量图，直到不存在增广路为止。整个过程中，每次增广的流量都会不小于上一次的增加量，因此需要满足连续增广，并且BFS成功与否决定了DFS会返回多大的可行流量。
三、应用
Dinic算法的应用主要在网络流中，可以求一个图中所有源点到汇点的最大流量（源点可能有多个），并且对于同一对源点-汇点，最多可以同时执行一次Dinic算法。
代码示例：
typedef int type; // 容量，类型名称视情况更改
struct edge
{
int to,rev;
type cap;
};
vector G[MAXV];
int iter[MAXV],level[MAXV];
void add_edge(int from,int to,type cap)
{
G[from].push_back((edge){to,(int)G[to].size(),cap});
G[to].push_back((edge){from,(int)G[from].size()-1,0});
}
void bfs(int s)
{
memset(level,-1,sizeof(level));
queue
q;
level[s]=0;
q.push(s);
while(!q.empty())
{
int v=q.front();
q.pop();
for(int i=0;i
0&&level[e.to]<0)
{
level[e.to]=level[v]+1;
q.push(e.to);
}
}
}
}
type dfs(int v,int t,type f)
{
if(v==t)return f;
for(int &i=iter[v];i
0&&level[v]
0)
{
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
type max_flow(int s,int t)
{
type flow=0;
for(;;)
{
bfs(s);
if(level[t]<0)return flow;
memset(iter,0,sizeof(iter));
type f;
while((f=dfs(s,t,INF))>0)
{
flow+=f;
}
}
}
四、优化
Dinic算法的常见优化方法有：
1.分层图（Level Graph）：最宽松的限制即每层只存储一次。即当前队列中存在两个点属于同一层，除非在更新某个点的距离后重新进行BFS，否则不会再向某层的点增加新的点。
2.在BFS时记录一组“pointer”，用于在DFS过程中从上次的返回点继续搜索，而不是从起点开始搜索。这种操作虽然为线性，但是其作用显然不及第一种优化（实际上第一种优化存在时间复杂度为O(n^2*m)的情况）。
3.使用最大流速度和一般的带宽不同，所以可以频繁的调整容量或者调整浮点数。最好还是针对不同的网络设置最适当的流媒体参数。
4.减弱其“最坏时间复杂度比某些算法还不如”的不足之一：采用HLPP算法
代码示例：
struct node
{
int v,f,nx;
}p[MAXM];
int head[MAXN],cur[MAXN],d[MAXN],cnt,n,m,S,T;
inline void add_edge(int u,int v,int f)
{
p[++cnt]=(node){v,f,head[u]};
head[u]=cnt;
p[++cnt]=(node){u,0,head[v]};
head[v]=cnt;
}
inline bool bfs()
{
for(re int i=S;i<=T;++i)
d[i]=-1,cur[i]=head[i];
queue q;
d[S]=0;
q.push(S);
while(q.size())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=p[i].nx)
{
int v=p[i].v,f=p[i].f;
if(d[v]==-1&&f)
{
q.push(v);
d[v]=d[u]+1;
if(v==T)
return 1;
}
}
}
return 0;
}
inline int dfs(int u,int flow)
{
if(u==T)
return flow;
int ret=flow;
for(int i=cur[u];i&&ret;i=p[i].nx)
{
cur[u]=i;
int v=p[i].v,f=p[i].f;
if(d[v]==d[u]+1&&f)
{
int w=dfs(v,min(ret,f));
p[i].f-=w;
p[i^1].f+=w;
ret-=w;
if(!ret)
break;
}
}
if(ret==flow)
d[u]=-2;
return flow-ret;
}
inline int dinic()
{
int ans=0;
while(bfs())
ans+=dfs(S,0x3f3f3f3f);
return ans;
}
五、总结
Dinic算法作为最大流算法的一种，能够在较优的时间内获得最大网络流，应用广泛。
在实战中，Dinic算法的时间复杂度也更有优势，而且最坏时间复杂度相对更小。Dinic在实际的网络流应用中占据相当重要的地位。
