本文主要是介绍关于Dinic算法的几点讨论，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
基本概念
Dinic算法是经典的网络最大流算法，该算法由在EK算法的基础上增加"分层"这一概念得到。算法复杂度为
，求解二分图最大匹配的时间复杂度为
算法过程
分层操作：
- 进行一次BFS。在BFS的过程中不断对未访问过的结点进行分层。
- 在分层的过程中，使用一个队列保存需要进行分层的点集，并用一个d[N]数组保存每个结点所在的层数。
算法主体（Dinic）：
- 在算法的主体过程中，我们只从层数编号较小的点到下一层的点。（可以证明，如果向层数较小的点"流"是无效的）
- 而Dinic算法的实质，是在DFS的过程中记录能流的最大流量。
最终，我们在不断分层和由源点进行Dinic算法的过程中获得了整体的最大流。
模板地址：https://www.luogu.org/problemnew/show/P3376
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=1000010,MAXM=1000010;
struct Edge{int from,to,w,nxt;
}e[MAXM];
int head[MAXN];
int edgeCnt=1;//反向边，所以边计数从1开始
void addEdge(int u,int v,int w){e[++edgeCnt].from=u;e[edgeCnt].to=v;e[edgeCnt].w=w;e[edgeCnt].nxt=head[u];head[u]=edgeCnt;
}
int s,t;
int d[MAXN];//层数
bool bfs(){queue<int> q;memset(d,0,sizeof(d));q.push(s);d[s]=1;while(!q.empty()){int nowNode=q.front();q.pop();for(int i=head[nowNode];i;i=e[i].nxt){int v=e[i].to;if(!d[v]&&e[i].w){q.push(v);d[v]=d[nowNode]+1;}}}return d[t]!=0;
}
int Dinic(int x,int flow){if(x==t)return flow;int rest=flow;for(int i=head[x];i&&rest;i=e[i].nxt){int v=e[i].to;if(d[v]==d[x]+1&&e[i].w!=0){int k=Dinic(v,min(rest,e[i].w));if(!k)d[v]=0;e[i].w-=k,e[i^1].w+=k;rest-=k; }}return flow-rest;
}
int INF=1<<30;
int main(){int n,m;scanf("%d%d%d%d",&n,&m,&s,&t);for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);addEdge(u,v,w);addEdge(v,u,0);}int nowFlow,ans=0;while(bfs())while(nowFlow=Dinic(s,INF))ans+=nowFlow;cout<<ans<<endl;return 0;
}
这篇关于关于Dinic算法的几点讨论的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
