• 最大流的四个算法框架,理论不需要解释了!原来实现的代码写的很烂,今天结合了《实用算法》上的实现来将算法实现和调试通过了,明天上午估计会耽搁一下,下午回来就继续把LRJ书上的题目一道一道的过掉。希望自己不看今天的代码框架一次做完,这些框架应该要非常熟悉才对!

1。一点改动:对于f(u,v)和f(v,u)而言,正负号判断让我很晕菜!先屏蔽到无效输入capcity=0的节点,OK,这样的节点对流的状态是不会有影响的。然后,仿照书上的例子把cap=-1时设置为标志位,若cap==-1则为反向边,Ef中g(v,u)=f(u,v),在f(u,v)>0时;正向边,Ef中g(u,v)=c(u,v)-f(u,v)。行,下面就可以实现了。

2。预处理头:

  • 公共的添边操作

#include <stdlib.h>
#include <iostream>
#include <fstream>

using namespace std;
const int MAXN=20, MAXE=400;

typedef struct Edge{
 int i, j, next, op, f, c;
};
Edge es[MAXE];
int eid=0, vid=0, first[MAXN], first1[MAXN], v, e, queue[MAXE], pre[MAXN], ptr[MAXN], hv[MAXN], ev[MAXN];//extra
int l[MAXN];
bool visited[MAXN];
//queue for bfs algorigthm, pre for each node in the queue, ptr for linked edge of each node!

//declaration
void addEdge(int i, int j, int c);

//common operation for adding edge, using int Edmond-Karp and Dicnic algorithm
void addEdge(int i, int j, int c){//i->j, and i<-j
 if(!c) return;
 es[eid].i=i, es[eid].j=j, es[eid].f=0, es[eid].c=c;
 es[eid].next=first[i], first[i]=eid;
 es[eid].op=eid+1, eid++;//set the opposite edge
 es[eid].i=j, es[eid].j=i, es[eid].f=0, es[eid].c=-1;//for opposite edge, default setting for capcity
 es[eid].next=first[j], first[j]=eid;
 es[eid].op=eid-1, eid++;
}

  • 残图更新逻辑:由于正向边反向边的更新逻辑一致,因此对于正向流,则f(u,v)+=dt(u,v),f(v,u)+=dt(u,v);而负向流,则为f(u,v)-=dt(u,v),f(v,u)-=dt(u,v)

3。主要算法详细实现

  • Ford-Fulkerson系最短路框架
算法1:基于Edmon-Karp算法框架(BFS的思路,使用BFS来生成最短路,算导上的表示)
算法伪码框架:[下午整理]
 
Edmond_Karp 算法:由于BFS的逻辑是基于一条随机最短路,因此其效率而言是四个算法中比较低的,但是有的时候也是一种可行算法。
     //初始化最大流的处理边逻辑
     while(find argumenting path from s to t in the residental graph){
             //寻找其路径最小值瓶颈Cf(u,v)
             //更新所有相关边,注意残图更新逻辑
     }
     //求出s的所有流出边,求出t的所有流入边,两者应该是一致的,均等于最大流的绝对值大小!
 
基于框架的实现代码:[已调试通过,复杂度O(E^2V)]

//implementation 1 : Edmond-Karp algorithm
void Edmond_Karp();

//simple implementation with BFS algorithm, O(VE^2).
void Edmond_Karp(){
 //create graph
 ifstream in("input.txt");
 if(!in) exit(EXIT_FAILURE);
 cin.rdbuf(in.rdbuf());
 cin>>v>>e;
 int start, end, cap;
 memset((void*)first, 0xff, sizeof(first));
 for(int i=0; i<e; i++){
  cin>>start>>end>>cap, addEdge(start, end, cap);
 }
 //BFS
 int top=0, size=1, maxflow=0, fmin;
 bool reachable=false;
 do{
  //BFS to find argumenting path from 0 to n-1 node,pre[1…n-1]记录其最大流边
  reachable=false, memset((void*)pre, 0xff, sizeof(pre));
  queue[top]=0, top=0, size=1, pre[top]=INT_MAX;
  while(top<size){
   int cur=queue[top++];//current node is v
   if(cur==v-1){reachable=true; break;}
   //here: orlando please dwell on why make the same mistake again! for node pre[es[i].j]!=pre[i];
   for(int i=first[cur]; i!=-1; i=es[i].next){
    if(pre[es[i].j]==-1&&(es[i].c>es[i].f||(es[i].c==-1&&es[i].f>0)))//not-visited and in the residental graph,残图判断逻辑
     pre[es[i].j]=cur, ptr[es[i].j]=i, queue[size++]=es[i].j;
   }
  }
  if(!reachable) break;
  //could reach n-1, backtrack to found path, and do updating
  //to find the fmin, one path backtrack
  fmin=INT_MAX;
  int edge=-1;
  for(int cur=v-1; cur!=0; cur=pre[cur]){//for v’s value
   if(es[ptr[cur]].c>es[ptr[cur]].f)
    if(es[ptr[cur]].c-es[ptr[cur]].f<fmin) fmin=es[ptr[cur]].c-es[ptr[cur]].f, edge=ptr[cur];
    else if(es[ptr[cur]].c==-1&&es[ptr[cur]].f>0)
     if(es[ptr[cur]].f<fmin) fmin=es[ptr[cur]].f, edge=ptr[cur];
  }
  //updating the value of agrumenting path,更新最大流的前向状态
  for(int cur=v-1; cur!=0; cur=pre[cur]){
   if(es[ptr[cur]].c>es[ptr[cur]].f)//正向流
    es[ptr[cur]].f+=fmin, es[es[ptr[cur]].op].f+=fmin;
   else if(es[ptr[cur]].c==0&&es[ptr[cur]].f>0)//反向流
    es[ptr[cur]].f-=fmin, es[es[ptr[cur]].op].f-=fmin;
  }
  maxflow+=fmin;
 }while(reachable);
 int t1=0, t2=0;
 for(int tmp=first[v-1]; tmp!=-1; tmp=es[tmp].next){
  t1+=es[tmp].f;
 }
 for(int tmp=first[v-1]; tmp!=-1; tmp=es[tmp].next){
  t2+=es[tmp].f;
 }
 cout<<"source ouput f : "<<t1<<endl;
 cout<<"dest input f : "<<t2<<endl;
 cout<<maxflow<<endl<<endl;
 in.close();
}
算法2:基于Dicnic算法框架(BFS生成标号,严格DFS的标号检查,算法书上有错,俄!让我郁闷了一小会儿)
算法伪码框架:[下午整理]
     //初始化最大流的处理边逻辑
     while(true){
             //bfs对每一个顶点进行距离标号,d[0]=0
             //若对于目标点无法标号,在bfs结束时,退出循环;
             //dfs求出多条从s到t的容许路径,d[i]=d[j]+1,求出最大流瓶颈值,更新所有流状态
             //退流是退到满流的上一个顶点,这样可以一次找到多个增广路
     }
     //求出s的所有流出边,求出t的所有流入边,两者应该是一致的,均等于最大流的绝对值大小! 
 
基于框架的实现代码:[已调试通过,复杂度O(V^2E)]
//implementation 2 : Dinic algorithm
void Dicnic();
void bfsLevel();//similar to d[i] label for minmal shortest path.bfs标号实现
void dfs_maxflow();//dfs的最大流实现
 
void Dicnic(){//refer to practise of Dicnic algorithm.
 //create graph, and cin binding operation
 ifstream in("input.txt");
 if(!in) exit(EXIT_FAILURE);
 cin.rdbuf(in.rdbuf());
 cin>>v>>e;
 int start, end, cap;
 eid=0, memset((void*)first, 0xff, sizeof(first));
 for(int i=0; i<e; i++){
  cin>>start>>end>>cap, addEdge(start, end, cap);
 }
 while(true){
  bfsLevel();
  if(pre[v-1]==INT_MAX) break;//n-1 with no dist[i] in queue
  dfs_maxflow();//dfs_maxflow(&maxflow), accumulate together 
 }
 int t1=0, t2=0;
 for(int tmp=first[0]; tmp!=-1; tmp=es[tmp].next){
  t1+=es[tmp].f;
 }
 cout<<"source ouput f : "<<t1<<endl;
 for(int tmp=first[v-1]; tmp!=-1; tmp=es[tmp].next){
  t2+=es[tmp].f;
 }
 cout<<"dest input f : "<<t2<<endl<<endl;
 in.close();
}
void bfsLevel(){//bfs for level, recording in pre[0…v-1] array
 for(int i=0; i<v; i++) pre[i]=INT_MAX;
 int top=0, size=1; queue[top]=0, pre[0]=0;
 while(top<size){
  int cv=queue[top++];
  if(cv==v-1) return;//pre[cv] has been set previously, similar to my code
  for(int ei=first[cv]; ei!=-1; ei=es[ei].next){
   if(pre[es[ei].j]>pre[cv]+1){//smart code
    if(es[ei].c>es[ei].f||(es[ei].c==-1&&es[ei].f>0))//add into queue
     queue[size++]=es[ei].j, pre[es[ei].j]=pre[cv]+1;
   }
  }
 }
}
//core implemenation : mix two logic together
void dfs_maxflow(){//书上逻辑有错,找到最大流后反向更新即可!
 memcpy((void*)first1, (void*)first, sizeof(first));
 memset((void*)visited, 0, sizeof(visited));
 int top=0; queue[0]=0;
 while(top>-1){
  if(queue[top]==v-1){//dfs find the n-1
   int fmint=INT_MAX, edge, tj;
   for(int j=top; j>0; j–){//down to 1
    if(es[ptr[queue[j]]].f<es[ptr[queue[j]]].c){
     if(es[ptr[queue[j]]].c-es[ptr[queue[j]]].f<fmint) fmint=es[ptr[queue[j]]].c-es[ptr[queue[j]]].f;
    }
    else if(es[ptr[queue[j]]].c==-1&&es[ptr[queue[j]]].f>0){
     if(es[ptr[queue[j]]].f<fmint) fmint=es[ptr[queue[j]]].f;
    }
   }
   for(int j=top; j>0; j–){
    if(es[ptr[queue[j]]].f<es[ptr[queue[j]]].c){
     es[ptr[queue[j]]].f+=fmint, es[es[ptr[queue[j]]].op].f+=fmint;
     if(es[ptr[queue[j]]].f==es[ptr[queue[j]]].c) tj=j;
    }
    else if(es[ptr[queue[j]]].c==0&&es[ptr[queue[j]]].f>0){
     es[ptr[queue[j]]].f-=fmint, es[es[ptr[queue[j]]].op].f-=fmint;     
     if(es[ptr[queue[j]]].f==0) tj=j;
    }
   }
   return;//比较原始的方法,每次只找一条增广路经
   top=tj-1;//回退到满流的上一个顶点,再次增广,Dicnic就这个比较valuable
  }
  else{
   int tmp=first1[queue[top]], tp=queue[top];
   for(;tmp!=-1; tmp=es[tmp].next){
    if(!visited[es[tmp].j]&&(pre[es[tmp].j]==pre[tp]+1)){
     if(es[tmp].f<es[tmp].c||(es[tmp].c==-1&&es[tmp].f>0)){
      first1[tp]=es[tmp].next;//modify next link, dfs recursive have to modify edge linkage
      queue[++top]=es[tmp].j, ptr[queue[top]]=tmp;
      break;
     }//if
    }
   }//for
   if(tmp==-1){visited[tp]=true; top–;}
  }
 }
}
 
  • 预流标进算法

通用的算法操作:

bool Relabel(int v);
bool Push(int e);

//实现代码 :对于余流节点的重标和push算法

bool Relabel(int u){//if we can relabel the node
 if(ev[u]<=0) return false;
 //in the residental graph
 int hmin=INT_MAX; bool minV=true;//最小高度,是否是最低点
 for(int e=first[u]; e!=-1; e=es[e].next){
  if(es[e].c>es[e].f||(es[e].c==-1&&es[e].f>0)){//in the residental graph
   if(hv[es[e].j]<hv[u]) minV=false;//hv[u]<=hv[es[e].j]
   if(hv[es[e].j]<hmin) hmin=hv[es[e].j];

  }
 }
 if(minV&&hmin<=v){hv[u]=hmin+1; return true; }//注意,这里v比|V|+1大一个距离,我们要考虑到比源点高度更高,这样所有的余流才有可能回流到源点之上.
 return false;
}
bool Push(int e){
 if(ev[es[e].i]<=0) return false;
 if(hv[es[e].i]==hv[es[e].j]+1){//for push operation
  int dt;
  if(es[e].f<es[e].c){
   dt=min(ev[es[e].i], es[e].c-es[e].f);
   es[e].f+=dt, es[es[e].op].f+=dt;
   ev[es[e].i]-=dt, ev[es[e].j]+=dt;
   return true;
  }
  if(es[e].c==-1&&es[e].f>0){
   dt=min(ev[es[e].i], es[e].f);
   es[e].f-=dt, es[es[e].op].f-=dt;
   ev[es[e].i]-=dt, ev[es[e].j]+=dt;//reverse-equal algorithm
   return true;
  }
 }
 return false;
}

算法3:基于Goldberg算法框架(简单的预流处理,基于顶点的随机验证)
算法伪码框架:[下午整理] 
     //初始化最大流的处理边逻辑,初始化源点的流边和顶点余流
     while(对于每一个可行顶点能找到relabel,或者push操作){
             //relabel或者push操作();
     }
     //求出s的所有流出边,求出t的所有流入边,两者应该是一致的,均等于最大流的绝对值大小!
 
基于框架的实现代码:[已调试通过,复杂度O(V^2E)]
//for random implemenation
void Goldberg(){
 ifstream in("input.txt");
 if(!in) exit(EXIT_FAILURE);
 cin.rdbuf(in.rdbuf());
 cin>>v>>e;
 int start, end, cap;
 eid=0, memset((void*)first, 0xff, sizeof(first));
 for(int i=0; i<e; i++){
  cin>>start>>end>>cap, addEdge(start, end, cap);
 }
 Initial();
 bool t=true;
 do{
  t=true;
  for(int i=1; i<v-1; i++){
   if(Relabel(i)) t=false;
   for(int e=first[i]; e!=-1; e=es[e].next)
    if(Push(e)) t=false;
  }
 }while(!t);
 int t1=0, t2=0;
 for(int tmp=first[0]; tmp!=-1; tmp=es[tmp].next){
  t1+=es[tmp].f;
 }
 cout<<"source ouput f : "<<t1<<" "<<ev[0]<<endl;
 for(int tmp=first[v-1]; tmp!=-1; tmp=es[tmp].next){
  t2+=es[tmp].f;
 }
 cout<<"dest input f : "<<t2<<" "<<ev[v-1]<<endl<<endl;
 in.close();
}
void Initial(){
 memset((void*)hv, 0, sizeof(hv)), memset((void*)ev, 0, sizeof(ev));
 hv[0]=v-1;//from 0 to v-1
 for(int e=first[0]; e!=-1; e=es[e].next){
  if(es[e].c>0){
   es[e].f+=es[e].c, es[es[e].op].f+=es[e].c;//for 0’s output stream
   ev[es[e].j]+=es[e].c, ev[0]-=es[e].c;
  }
 }
}
 
算法4:基于群牛算法框架(最高标号,预流标进)
算法伪码框架:[下午整理]
     //初始化最大流的处理边逻辑
     //初始化L随机队列(除开0,以及v-1),由于在最大流边形成之中,已经生成了相邻边逻辑,因此下面可以省去!
     while(u!=-1){
           int oldheight=hv[u];
           Discharge(u);//核心操作discharge(u)
           if(oldheight变化) 将u调整到L队列头
           u=L-next(u);//记录其边位置即可
     }
     //求出s的所有流出边,求出t的所有流入边,两者应该是一致的,均等于最大流的绝对值大小!
 
基于框架的实现代码:[已调试通过,复杂度O(V^3)->渐进意义:O(V^2M^1/2)]
//implemenation 4 : HighestPreflow
void Relabel_to_front();
void Initialize_preflow();
void Discharge(int u);//if old-height can be changed any more!
//notes: HighestPreflow implemented by linklist
void Relabel_to_front(){
 Initialize_preflow();
 int pos=0, u=l[pos];
 while(u!=-1){
  int oldh=hv[u];
  Discharge(u);
  if(hv[u]>oldh){
   //switch pos and 0
   if(pos!=0) l[pos]^=l[0], l[0]^=l[pos], l[pos]^=l[0];
   pos=0;
  }
  u=l[++pos];
 }
 int t1=0, t2=0;
 for(int tmp=first[0]; tmp!=-1; tmp=es[tmp].next){
  t1+=es[tmp].f;//非常重要的性质:所有中间结点的ev[es[e].j]==0
 }
 cout<<"source ouput f : "<<t1<<" "<<ev[0]<<endl;
 for(int tmp=first[v-1]; tmp!=-1; tmp=es[tmp].next){
  t2+=es[tmp].f;
 }
 cout<<"dest input f : "<<t2<<" "<<ev[v-1]<<endl<<endl;
}
void Discharge(int u){//discharge for u
 int tmp=first[u];
 while(ev[u]>0){
  if(tmp==-1) Relabel(u), tmp=first[u];//for relabel
  else if((es[tmp].c>es[tmp].f||(es[tmp].c==-1&&es[tmp].f>0))&&hv[u]==hv[es[tmp].j]+1)
   Push(tmp);
  else tmp=es[tmp].next;
 }
}
void Initialize_preflow(){
 ifstream in("input.txt");
 if(!in) exit(EXIT_FAILURE);
 cin.rdbuf(in.rdbuf());
 cin>>v>>e;
 int start, end, cap;
 eid=0, vid=0, memset((void*)first, 0xff, sizeof(first));
 for(int i=0; i<e; i++){
  cin>>start>>end>>cap, addEdge(start, end, cap);
 }
 memset((void*)l, 0xff, sizeof(l));
 for(int i=0; i<v-2; i++) l[i]=i+1;
 //for hv and ev
 memset((void*)hv, 0, sizeof(hv)), memset((void*)ev, 0, sizeof(ev));
 hv[0]=v-1;
 for(int e=first[0]; e!=-1; e=es[e].next){
  if(es[e].c>0){
   es[e].f+=es[e].c, es[es[e].op].f+=es[e].c;
   ev[es[e].j]+=es[e].c, ev[0]-=es[e].c;
  }
 }
 in.close();
}
  • 以后的算法,主要选用Dicnic最高预流标进,所以请熟练掌握,如果不能一次写完无bugs,请删掉重来!

Advertisements