前面的的几篇关于网络流的我被坑了，原来我用的算法叫做EK

下面总结下网络流的模板吧

1 #include 
     
       2 #include 
      
        3 //#include 
       
         4 using namespace std; 5 #define arraysize 201 6 int maxData = 0x7fffffff; 7 int capacity[arraysize][arraysize]; //记录残留网络的容量  8 int flow[arraysize];                //标记从源点到当前节点实际还剩多少流量可用 9 int pre[arraysize];                 //标记在这条路径上当前节点的前驱,同时标记该节点是否在队列中 10 int n,m;11 queue
        
          myqueue;12 int BFS(int src,int des)            //EK算法使用BFS寻找增广路径 13 {14     int i,j;15     while(!myqueue.empty())         //队列清空 16         myqueue.pop();17     for(i=1;i
         
          0 && pre[i]==-1)33             {34                  pre[i] = index;              //记录前驱 35                  flow[i] = min(capacity[index][i],flow[index]);   //关键：迭代的找到增量 36                  myqueue.push(i);               37             }38         }39     } 40     if(pre[des]==-1)      //残留图中不再存在增广路径  41         return -1;42     else43         return flow[des];44 }45 int maxFlow(int src,int des)46 {47     int increasement= 0;48     int sumflow = 0;49     while((increasement=BFS(src,des))!=-1)50     {51          int k = des;          //利用前驱寻找路径 52          while(k!=src)53          {54               int last = pre[k];55               capacity[last][k] -= increasement; //改变正向边的容量 56               capacity[k][last] += increasement; //改变反向边的容量 57               k = last;58          }59          sumflow += increasement;60     }    61     return sumflow;62 }
         
        
       
      
     

这个算法要好好学习下