网络流模板.cpp

/*
网络流 之 最大流 增广路算法  http://blog.163.com/art_budder_niu/blog/static/1393646202010322115138703/
FF算法：分为三个步骤，首先寻找一条增广路（如果没有增广路，则返回最大流），同时保存路径；其次，对路径上的流量求最小值，记为min；最后根据路径修改网络，对于前向边，减去最小值，对于后向边，加上最小值，或者直接修改容量。

增广路：从源点s到汇点t的一条有向路径，如果从源点开始不可以到汇点，那么没有增广路。

保存：用一个数组保存，一般是采用父亲表示法（父链接），保存当前节点的父亲， 寻找的时候采用的是迭代的方式实现求最小值以及修改原网络。

寻找增广路，采用bfs的方式。详细算法如下：
*/
#include <iostream>
#include <queue>
using namespace std;
 
const int N = 210;
const int INF = 0x7FFFFFFF;
int n,m,map[N][N],path[N],flow[N],start,end;
queue<int> q;

int bfs(){
     int i,t;
     while(!q.empty()) q.pop();   //清空队列
     memset(path,-1,sizeof(path));  //保存父亲的数组，初始化为-1
     path[start]=0,flow[start]=INF;   //flow[] 保存当前的最小容量
     q.push(start);
     while(!q.empty()){
         t=q.front();
         q.pop();
         if(t==end) break;   //找到一条增广路
         for(i=1;i<=m;i++){
             if(i!=start && path[i]==-1 && map[t][i]){
                 flow[i]=flow[t]<map[t][i]?flow[t]:map[t][i];
                 q.push(i);
                 path[i]=t;
             }
         }
     }
     if(path[end]==-1) return -1;   //如果汇点的父亲等于-1，说明不能到达最后。
     return flow[m];                   //一次遍历之后的流量增量，min
 }
 int Edmonds_Karp(){
     int max_flow=0,step,now,pre;
     while((step=bfs())!=-1){          //找不到增路径时退出
         max_flow+=step;
         now=end;
         while(now!=start){
             pre=path[now];
             map[pre][now]-=step;      //更新正向边的实际容量
             map[now][pre]+=step;      //添加反向边
             now=pre;
         }
     }
     return max_flow;
 }
 int main(){
     int i,u,v,cost;
     while(scanf("%d %d",&n,&m)!=EOF){
         memset(map,0,sizeof(map));
         for(i=0;i<n;i++){
             scanf("%d %d %d",&u,&v,&cost);
             map[u][v]+=cost;           //not just only one input
         }
         start=1,end=m;
         printf("%d\n",Edmonds_Karp());
     }
     return 0;
 }

/*
主要分为模块三个：

模块1：

int FF()

{

     while(有增广路){

          更新原图的前向边（减min），后向边（+min），同时保存最大流的增量值。

         }

        返回最大流值。

}

模块2：

int agument_path()

{

     源点进队；

    while（队列不空）

    {  出队；

      如果达到汇点，则结束；

      for(i=1;i<=m;i++){ 

      //搜索整个图的邻接边

     如果未保存，且边不为0（可增的量），且不是开始节点

             进队，保存，求最小值

    }

    如果汇点的父亲没有，说明没有增广路，返回-1；

   返回最小值；

}

 

模块3：

building{

for(i=0;i<n;i++){
             scanf("%d %d %d",&u,&v,&cost);
             map[u][v]+=cost;           //not just only one input

}
最大流的建图思想：对于每条边，直接累加其容量就可以了。
*/