本文共 2229 字，大约阅读时间需要 7 分钟。
/*题目大意：求一个图中起点s到终点t的最大流除以s到t的的所有路径中的最大流量的那条路径流量值； （虽然这样看起来比较简单，但说实话，这题我读题至少都花了半个小时，直到ac的的前一秒我都有点怕题意读错） 此题主要要求两个量：整个图的最大流和一路径的最大流量值； 最大流maxflow没什么好说的，直接套模板（不过此题完全照搬是不行的，需要做一点修改）， 虽然我本打算自己去实现的练练手的，但是当我正打算手动实现的时候，阮学长建议我大比赛的 时侯有模板尽量用模板，所以我就去拿到了那本模板书， 照着敲，发现这模板却是写得好，要让我敲得话， 肯定至少得花一个小时左右！完全套模板的不能ac的原因是： 这题的head[i]存放的是-1，而模板却是把它作为0来处理的， 所以的对模板做了一下修改！ 另外在敲得过程中发现他的cur[MAXN]纯粹属于浪费空间，果断删除！ 一路径的最大流量值maxedge，之前阮学长打算以求最大路径的方法来求这个值，当我看到他用到spafa算法的时候， 我就知道他这里可能理解错了，所以和他讨论，他也将他的代码删掉了，后来讨论用深搜的方法求， 但是感觉 有环，处理起来很麻烦，阮和王相去讨论另一道题了，之后我又想了想， 为什么不在求最大流的时候，注入我的maxedge，后来果断打擂方式，一较短的代码一次性ac！ 虽然最大网络流都已经是很经典的模板了，感觉没多大必要讲的，但是有考虑到如果只会套模板， 不知里面的工作原理，在正式比赛中很难随需求任意修改模板里面的处理细节！ 所以我还是在下面大概说一下最大流的一种比较经典的，也比较实用的一个网络流算法吧 第一步：以原点s为根节点，将所有的节点按深度分层，（这个模板有个比较beautiful的地方就是利用路径数组ps来做队列 ，节省了很大的空间）直到将汇点t找到为止，如果直到最后都没找到t那 说明没有路径了！最大流搞定！ 第二部：从s开始，一 层一层的向下寻找t，找到之后，求出最小容量边tr，以此为流量将各边减去tr，在将各边的反向边加tr！ 跳到第三步； 第三部： 回溯到f点（f点是满足离s最近且，以该点为端点的边容量被减为了0）；之后跳到第二步,继续寻找到t的路径!当找不到t的时候， 又跳到第一步； 注解提供者：GHQ（SpringWater） */#include#include #define MAXN 20#define MAXE 40#define typec intconst typec inf = 0x3f3f3f3f;struct edge{int x,y,nxt; typec c;}bf[MAXE];//bf用来查找某节点相连的所有节点int ne,head[MAXN],ps[MAXN],dep[MAXN];void addedge(int x,int y,typec c){ bf[ne].x=x;bf[ne].y=y;bf[ne].c=c; bf[ne].nxt=head[x];head[x]=ne++; bf[ne].x=y;bf[ne].y=x;bf[ne].c=0; bf[ne].nxt=head[y];head[y]=ne++;}typec flow(int n,int s,int t){ typec tr,res=0; int i,j,k,l,r,top; while(1){ memset(dep,-1,n*sizeof(int)); for(l=dep[ps[0]=s]=0,r=1;l!=r;)//该部分为分层，dep[i]表示节点i在第几层， //而用到ps[l,r]在 这里做广搜 的队列l表示队列左边 ，r表示队列的右边； { for(i=ps[l++],j=head[i];j!=-1;j=bf[j].nxt)//i为从队列头取一个元素赋值给i { if(bf[j].c&&-1==dep[k=bf[j].y]){//当找到一个点相邻点，却流量不为0，同时还没有被分层！ dep[k]=dep[i]+1;ps[r++]=k; if(k==t)//当发现汇点已经被分层，则结束分层， { l=r; break; } } } } if(dep[t]==-1)break;//当发现不能分层，说明已经找不到汇点，最大网络流结束！ for(i=s,top=0;;) { if(i==t)//当一层层的深搜，找到了t，则需找出s到t路径中的最小容量tr，正向边减去该tr，反向边加上tr { for(k=0,tr=inf;k
转载地址：http://vhuvi.baihongyu.com/