网络流最大流算法dinic
ps：本文章不适合萌新，我写这个主要是为了复习一些细节，概念介绍比较模糊，建议多刷题去理解
例题：codevs草地排水，方格取数
【抒情一下】
虽然老师说这个多半不考，但是学了没坏处，所以我就把这算法学了（准确说是补起了QAQ）
以前一直觉得dinic的代码好长好难啊，然后就知难而退
最近学了很多和看了很多以后，咱们就学会了知男♂而上了，所以我果断的回来上dinic了
【dinic】
Dinic算法是用来做最大流一类题的，代码有一丢丢的长，但其实说白了就是一个bfs+dfs就没了，所以没必要有啥心理负担
我们先来画一个图，我们需要从1点流到n点
首先看这个图，每条边上标的是这条边的容量
Dinic的想法就是对当前图去找一条还能够从s通往t的可行路
然后可行路可以由图中的边组成，也可以用图中的边的逆向边组成
至于为什么要建立逆向边和逆向边的含义，我们重新画一张图
我假设这张图的目前的流量为
E(s,2)=0,E(s,1)=4,E(1,2)=2,E(2,t)=2,E(1,t)=2;
然后我们建立逆向边或者说是反向弧，就是沿着箭头的反方向建边，反向边的容量为正向边的流量（不是容量）
所以当前反向边的容量为
E(2,s)=0,E(1,s)=4,E(2,1)=2,E(t,2)=2,E(t,1)=2;
然后为什么要建立这些边，我们先看图，当前的图肯定不是最优的，这时候就要找增广路
增广路简单一点理解就是还有一条从s到t的路
然后我们发现边s,1是满的，所以找到可以流的边s,2的流量是0，然后到2点发现2,1边的容量是2（因为E(1,2)=2,所以反向此时的容量为2），最后发现1,t边容量4流量2，于是找到一条增广路
S->2->1->t，这条增广路可以扩大2的流量，所以最大流+2，为6
至于程序也很简单，首先是建图，建完图以后一个while循环（用bfs判断），bfs的过程是找还有没有增广路，然后在循环内dfs，dfs是找这条增广路的可以扩大的最大流量
至于在dfs判断是否是我们找出的合法路径，可以在bfs是对路径加深度，如果容量大于流量并且不是同一深度，那么dfs就可以继续搜索下去
然后我给一个dinic的模版，模板题就用草地排水了
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<iostream>
5 #include<queue>
6 #include<cmath>
7 #include<cstdlib>
8 #include<stack>
9 #define maxn 505
10 using namespace std;
11
12 queue<int>q;
13 int c[maxn],head[maxn],f[maxn],n,m,dep[maxn],ans;
14 struct edge{
15 int u,v,w,nxt,flow;
16 }e[maxn];
17
18 int read(){
19 int xx=0,ff=1;char ch=getchar();
20 while(ch<'0'||ch>'9'){if(ch=='-')ff=-1;ch=getchar();}
21 while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
22 return xx*ff;
23 }
24
25 int tot=1;
26 void adde(int u,int v,int w){
27 e[++tot].u=u;
28 c[tot]=w;
29 e[tot].v=v;e[tot].w=w;
30 e[tot].nxt=head[u];
31 head[u]=tot;
32 }
33
34 int bfs(){
35 q.push(1);
36 memset(dep,-1,sizeof(dep));
37 dep[1]=0;
38 while(!q.empty()){
39 int u=q.front();q.pop();
40 for(int i=head[u];i!=-1;i=e[i].nxt){
41 int v=e[i].v;
42 if(dep[v]==-1&&c[i]-f[i]){
43 dep[v]=dep[u]+1;
44 q.push(v);
45 }
46 }
47 }
48 if(dep[n]==-1)return 0;
49 else return 1;
50 }
51
52 int dfs(int u,int lim){
53 if(u==n){ans+=lim;return lim;}
54 int t;
55 for(int i=head[u];i!=-1;i=e[i].nxt ){
56 int v=e[i].v;
57 if(c[i]-f[i]&&dep[u]+1==dep[v]&&(t=dfs(v,min(lim,c[i]-f[i])))){
58 f[i]+=t;f[i^1]-=t;return t;
59 }
60 }
61 return 0;
62 }
63
64 int main(){
65 memset(head,-1,sizeof(head));
66 m=read();n=read();
67 for(int i=1;i<=m;i++){
68 int u,v,w;
69 u=read();v=read();w=read();
70 adde(u,v,w);adde(v,u,0);
71 }
72 while(bfs()){
73 dfs(1,0x3f3f3f);
74 }
75 printf("%d",ans);
76 }
【总结】
网络流的难点在于建图，这个另类的建图可以参加一下方格取数，拓宽一下视野