题目链接：https://www.luogu.com.cn/problem/P3376
参考博客：https://www.cnblogs.com/SYCstudio/p/7260613.html
最大流Dinic算法，在EdmondsKarp算法的基础上加上了BFS层次图的概念，使得增广更加有方向，并且在一次DFS中可以寻找到多条增广路，算法的复杂度是O(|E|*|V|^2)，但是实际上算法的速度比理论的时间复杂度说明的时间要快。Dinic算法的思想是这样的，对于每个点，如果他有许多分支的话可以每次对每一个分支都进行一次增广路搜索，而不是要从src点从头开始增广。每次dfs一个分支之后都会退回到当前点，此时可以更新这个分支用掉的流量的大小，下一个分支可用的流量便减少了。
代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned int ui; 4 typedef long long ll; 5 typedef unsigned long long ull; 6 #define pf printf 7 #define mem(a,b) memset(a,b,sizeof(a)) 8 #define prime1 1e9+7 9 #define prime2 1e9+9 10 #define pi 3.14159265 11 #define lson l,mid,rt<<1 12 #define rson mid+1,r,rt<<1|1 13 #define scand(x) scanf("%llf",&x) 14 #define f(i,a,b) for(int i=a;i<=b;i++) 15 #define scan(a) scanf("%d",&a) 16 #define mp(a,b) make_pair((a),(b)) 17 #define P pair<int,int> 18 #define dbg(args) cout<<#args<<":"<<args<<endl; 19 #define inf 0x7ffffff 20 inline int read(){ 21 int ans=0,w=1; 22 char ch=getchar(); 23 while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();} 24 while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar(); 25 return ans*w; 26 } 27 28 const int maxn=1e5+10; 29 int n,m,s,t; 30 int cnt=0; 31 int head[maxn],nxt[maxn*10],d[maxn]; 32 struct node{ 33 int v,w; 34 }p[maxn*10]; 35 int e; 36 void addedge(int u,int v,int w) 37 { 38 p[e].v=v; 39 p[e].w=w; 40 nxt[e]=head[u]; 41 head[u]=e++; 42 } 43 bool bfs(int src,int sink)//确定bfs序 44 { 45 mem(d,0); 46 d[src]=1; 47 queue<int> q; 48 q.push(src); 49 while(!q.empty()) 50 { 51 int cur=q.front(); 52 q.pop(); 53 for(int i=head[cur];~i;i=nxt[i]) 54 { 55 int v=p[i].v; 56 if(!d[v]&&p[i].w)//确定这个点没有被标号，并且不是反向边 57 { 58 d[v]=d[cur]+1; 59 q.push(v); 60 } 61 } 62 } 63 if(d[sink])return true; 64 return false; 65 } 66 int dfs(int s,int flow) 67 { 68 if(s==t)return flow; 69 int used=0; 70 for(int i=head[s];~i;i=nxt[i]) 71 { 72 int v=p[i].v,w=p[i].w; 73 if(d[v]==d[s]+1&&w>0)//根据Dinic算法的思想，只能走正向的、bfs序大一的边 74 { 75 int tmp=dfs(v,min(flow-used,w)); 76 if(tmp>0) 77 { 78 p[i].w-=tmp;//更新正向边的流量以及反向边的流量， 79 p[i^1].w+=tmp;//正向边是偶数，它对应的反向边就是正向边+1 80 used+=tmp;//从一个点出发最多的流量是flow，用掉的流量需要更新 81 if(used==flow)break; 82 } 83 } 84 } 85 return used; 86 } 87 int dinic() 88 { 89 int ans=0; 90 while(bfs(s,t)) 91 { 92 ans+=dfs(s,inf); 93 } 94 return ans; 95 } 96 int main() 97 { 98 //freopen("input.txt","r",stdin); 99 //freopen("output.txt","w",stdout); 100 std::ios::sync_with_stdio(false); 101 n=read(),m=read(),s=read(),t=read(); 102 mem(head,-1);mem(nxt,-1); 103 int u,v,w; 104 f(i,1,m) 105 { 106 u=read(),v=read(),w=read(); 107 addedge(u,v,w);addedge(v,u,0); 108 } 109 int maxflow=dinic(); 110 pf("%d ",maxflow); 111 }