P3376 【模板】网络最大流

传送门

$dinic$算法调了一天，有许多细节需要注意。

思路：$dinic$算法，相比$EK$算法，时间复杂度从$O(n{m}^2)\to O(n^{2}m)$

十分地优秀，

因为$EK$算法是一次$bfs$找到一条增广路，再$dfs$求最大流十分麻烦。

而$dinic$算法是一次$bfs$给图分层，然后$dfs$同时找多条增广路求最大流。

$bfs$不能将终点分层时则可以结束了。

---

优化1：当剩余路径的最大流量是$0$时，我们可以将$dep[v]$置为1，这样就不用再走这条路了。对应代码：$if(!now)dep[v]=1;$

---

优化2：当总的剩余流是$0$时，说明我们已经不能再使其最大流更大了，直接返回当前最大流即可。对应代码： $if(!res)returnflow;$

---

优化3：弧优化，如果前$i-1$条弧已经走过了，说明他们已经是最大流了，所以下此再搜时可以直接从这条弧开始，这里我们用类似$head[]$数组来构建一个$cur[]$数组来维护的。

注意写的时候：要在循环里写$cur[u]=i$,而不能写$cur[u]=e[i].nt$。

因为可能下面的$dfs(v,min(res,w))$还需要用前面的弧。这样把该弧的所有情况都遍历完了，才能$cur[i]=e[i].nt$。

或者直接换个写法：$for(int\&i=cur[u];i;i=e[i].nt)$

这里我调试了好半天才发现。

---

此外我们需要注意的时，再对残留网络进行建立反边时，要注意边的初始编号要从偶数开始，因为根据异或性质$2\oplus 1=3,3\oplus 1=2$.

这样才能正反边建立起对应关系。

还有这题结果可能会爆$int$，开个$longlong$就行。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2000+10,M=1e4+5,mod=1e9+7; #define mst(a) memset(a,0,sizeof a) #define fmst(a) memset(a,-1,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second int n,m,s,t,h[N],cur[N],cnt=1,dep[N]; struct node{ int to,nt,w; }e[M]; void add(int u,int v,int w){ e[++cnt]={v,h[u],w},h[u]=cnt; } queue<int>q; bool bfs(){ //给图分层. mst(dep); dep[s]=1;q.push(s); while(!q.empty()){ int u=q.front();q.pop(); cur[u]=h[u]; //每次初始化cur[] for(int i=h[u];i;i=e[i].nt){ int v=e[i].to,w=e[i].w; if(w&&!dep[v]) dep[v]=dep[u]+1,q.push(v); } } return dep[t]; } int dfs(int u,int flow){ if(u==t)return flow; int res=flow; for(int &i=cur[u];i;i=e[i].nt){ //优化3. int v=e[i].to,w=e[i].w; if(w&&dep[u]+1==dep[v]){ int now=dfs(v,min(res,w)); //这里有个小细节要用res而不是flow，因为要取到当前最小,flow可能不是最小的. if(!now) dep[v]=1; //优化1 else{ e[i].w-=now; //建立反边. e[i^1].w+=now; res-=now; } } if(!res)return flow; //优化2 } return flow-res; } int main(){ scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1,u,v,w;i<=m;i++){ scanf("%d%d%d",&u,&v,&w); add(u,v,w),add(v,u,0);//反边初始化为0,因为总流量为正流量-反流量. } ll ans=0; while(bfs())ans+=dfs(s,0x7fffffff); printf("%lld\n",ans); return 0; }