网络最大流dinic算法优化

前置知识

不会最大流板子的出门右转：https://www.cnblogs.com/yinyuqin/p/14508965.html

小优化

Dinic除了当前弧优化外，还有一点小优化（来自nealchen）：在进行bfs分层时，从t点开始搜索分层，搜到s就直接停止搜索。

因为剩下的未分层的点的层数一定大于等于s点，dfs时不会搜索到，所以可以大胆省去。

于是就有了一点点优化：

原来的：

现在的：

能看出来？

注意原来分层中条件e[i].cap>0变成了e[i^1].cap>0。

代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<stack>
 7 #include<set>
 8 #include<queue>
 9 const int maxn=205;
10 int n,m,s,t,cnt=1,dis[maxn],cur[maxn],p[maxn];
11 long long ans;
12 using namespace std;
13 struct node{
14     int v,next;
15     long long cap;
16 }e[10005];
17 void insert(int u,int v,int w){
18     cnt++;
19     e[cnt].v=v;
20     e[cnt].next=p[u];
21     e[cnt].cap=w;
22     p[u]=cnt;
23 }
24 bool bfs(){
25     memset(dis,0,sizeof(dis));
26     dis[t]=1;
27     queue<int> q;
28     q.push(t);
29     while(!q.empty()){
30         int u=q.front();
31         q.pop();
32         for(int i=p[u];i!=-1;i=e[i].next){
33             if(e[i^1].cap<=0) continue;
34             int v=e[i].v;
35             if(!dis[v]){
36                 dis[v]=dis[u]+1;
37                 q.push(v);
38                 if(v==s) return 1;
39             }
40         }
41     }
42     return 0;
43 }
44 long long dfs(int u,long long maxflow){
45     if(u==t||maxflow==0) return maxflow;
46     long long f=0;
47     for(int &i=cur[u];i!=-1;i=e[i].next){
48         int v=e[i].v;
49         if(dis[v]==dis[u]-1&&e[i].cap>0){
50             long long flow=dfs(v,min(maxflow,e[i].cap));
51             maxflow-=flow;
52             e[i].cap-=flow;
53             e[i^1].cap+=flow;
54             f+=flow;
55             if(maxflow==0) break;
56         }
57     }
58     return f;
59 }
60 void dinic(){
61     while(bfs()){
62         for(int i=1;i<=n;i++) cur[i]=p[i];
63         ans+=dfs(s,1e15);
64     }
65 }
66 int main(){
67     memset(p,-1,sizeof(p));
68     scanf("%d%d%d%d",&n,&m,&s,&t);
69     for(int i=1;i<=m;i++){
70         int u,v,w;
71         scanf("%d%d%d",&u,&v,&w);
72         insert(u,v,w);
73         insert(v,u,0);
74     }
75     dinic();
76     cout<<ans;
77     return 0;
78 }