【算法】网络最大流EK

网络流是干嘛的？举一个例子：在一个水上城市中，有很多小镇，之间有很多座桥连着，每一座桥因为制作材料不同最大载重不同，如果超过最大载重，桥就垮了，桥上的人就GG了，所以我们不能让这样

网络流是干嘛的？举一个例子：

在一个水上城市中，有很多小镇，之间有很多座桥连着，每一座桥因为制作材料不同最大载重不同，如果超过最大载重，桥就垮了，桥上的人就GG了，所以我们不能让这样的情况发生——即：每一条边的流量不能超过容量，我们再规定一个起点，一个终点，我们要从起点运货到终点，只有一次机会但可以同时走多条道路充分利用资源，最后求：最大运货量可以为多少？

这就是网络最大流问题，求某点到某点的最大流量。

EK算法，网络流最朴素的算法，不断寻找增广路，再来回两遍减容量，加ans，容易理解：

1 #include 2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int MAXN=200+10,inf=2000000000; 8 int c[MAXN][MAXN],f[MAXN][MAXN],q[MAXN][2],n,m,ans;//c数组是记录容量，f数组是记录流量，q为队列，因为既要记录当前点，也要记录路径，所以开2维 9 bool p[MAXN],mark=true;//p代表每个点是否可取（每个点只能取一次）10 inline void read(int 13 char c=getchar();14 while(c‘9‘)c=getchar();15 while(c>=‘0‘18 c=getchar();19 }20 }21 int main()22 {23 read(m);read(n);24 for(register int i=1;i<=m;++i)//输入容量，没有连通的容量就为025 {26 int x,y,z;27 read(x);read(y);read(z);28 c[x][y]+=z;//有可能两个点之间有多条管道29 }30 while(mark)31 {32 mark=false;33 for(register int i=1;i<=n;++i)p[i]=true;//把每个点都设为可取34 p[1]=false;//把1取走35 q[1][0]=1;//放入队列36 q[1][1]=0;//1的前面路径为037 int head=0,tail=1;//队列的头和尾38 while(head0))//判断如果该点可取并且容量大于流量（因为f初始化为0，而不连通的两点c数组的值也为0，所以不会计入）或当前方向为反向时（反向没有容量）判断正向是否有流量，若有流量则代表有容量45 {46 p[i]=false;//设为不可取47 q[++tail][0]=i;//放入队列48 q[tail][1]=head;//记录路径（注意：存的是head，即当前点在队列中的位置）49 if(i==n)//如果当前点是终点，那么已经找到了一条路径50 {51 mark=true;52 break;//直接跳出循环53 }54 }55 }56 if(mark)break;57 }58 if(!mark)break;//如果找不到路径了，就是都搜完了，就跳出循环59 int minn=inf,pos=tail;//minn代表瓶颈，pos从终点向前找60 while(q[pos][1])//走第二遍，从后往前寻找瓶颈 //只要当前点的前面还有点61 {62 int x=q[q[pos][1]][0],y=q[pos][0];//x，y为一条管道的两个端点，x为前面的点，y为后面的点63 if(c[x][y]>f[x][y])minn=min(minn,c[x][y]-f[x][y]);//如果容量大于流量，即还可以流，那么更新瓶颈64 else if(f[y][x]>0)minn=min(minn,f[y][x]);//另一种情况，反向流量最大为正向流量65 pos=q[pos][1];//进行下一个点的搜索66 }67 pos=tail;68 while(q[pos][1])//走第三遍，更改路径上的流量69 {70 int x=q[q[pos][1]][0],y=q[pos][0];71 if(c[x][y]>f[x][y])f[x][y]+=minn;//正向，（正向）流量加上瓶颈72 else f[y][x]-=minn;//反向，（正向）流量减去瓶颈73 pos=q[pos][1];74 }75 }76 for(register int i=2;i<=n;++i)ans+=f[1][i];//从起点流出的必会流到终点，起点（或终点）的所有流量即为最大流77 printf("%d",ans);78 return 0;79 }网络最大流 EK

【算法】网络最大流 EK