dinic

#include<stdio.h>   #include<string.h>   #define MAXN 20   #define MAXE 40   #define typec int   const 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<top;++k)//路径边的编号保存在 ps[top]里，                       if(bf[ps[k]].c<tr)tr=bf[ps[l=k]].c; //打雷获得最小tr，注意这里的 l=k，l将记录路径ps【l】                                                           //可以起到找到里s最近的那个正向边减去tr为0的点bf[ps[l]].x，方便后面回溯！(使增广路径后退至p中从源点可到达的最后一个顶点。)                       for(k=0;k<top;++k)//正向边减tr，反向变加tr                           bf[ps[k]].c-=tr,bf[ps[k]^1].c+=tr;                       res+=tr;i=bf[ps[top=l]].x;//最大流res+tr，并将回溯到的目标点，赋值 给当前点i               }               for(j=head[i];j!=-1;j=bf[j].nxt)//从当前点i找一个可以到达的点bf[j].y                   if(bf[j].c&&dep[i]+1==dep[bf[j].y])break;               if(j!=-1)//当找到一个可以到达的点，则可以跳到下一层，把当前点i改变为下一层的点bf[j].y，并将j放到为路径ps堆栈里               {                   ps[top++]=j;//将j放到为路径ps堆栈里                   i=bf[j].y;//当前点i改变为下一层的点bf[j].y               }               else//当当前 i点，不能跳转到下一层，则需要回溯               {                   if(!top)break;//当路径堆栈top==0时，说明i==s点，无法回溯！                   dep[i]=-1;i=bf[ps[--top]].x;//否则存在可回溯点，因为当前点i在该种分层法则不行的，                                          //可将dep[i]除掉（dep[i]=-1）,再将回溯的bf[ps[--top]].x点复制给i！               }           }       }       return res;   }   int main()   {       int T,cas,e,s,t,n,maxflow,i;       int x,y,c;       double ans;       scanf("%d",&T);       while(T--)       {           scanf("%d%d%d%d",&n,&e,&s,&t);           memset(head,-1,sizeof(head));           for(i=ne=0;i<e;i++)           {               scanf("%d%d%d",&x,&y,&c);               addedge(x,y,c);           }           int maxedge=0;           maxflow=flow(n,s,t);           ans=(double)maxflow/(double)maxedge;           printf("%0.3lf\n",ans);                  }       return 0;  

}

1：分层，2：找增广路，然后回溯。找不到了以后，返回1。直到无法分层