• 提出这个部分主要是针对最大流最小割的几个典型应用,而这几点在算导和黑书上没有详细描述。
  • 这里沿用《实用算法》上的三个典型应用:图的割切图的连通度图的边连通度。顺便把多源多汇的可行流容量上下界的最大流,最小路径覆盖[多源多汇的改造问题],以及最小费用最大流问题一起描述并实现了。[最小费用问题也可以用线型规划来解,就像差分也可以不用图而用线型规划来解,都是相通的。]
  • 这块有点太理论了,不过还是都实现一遍吧,最大流的难点在建模,编程都还在其次。但编程是基本功,还在其次的问题都不能秒杀,谈什么建模呢?

1.最小割(S,T)的解法:当流稳定时,换言之,从S出发无法找到一个前向流,使得当前流f再增加。定义残存前向图Df,边集Ef={(u,v)属于E,c(u,v)-f(u,v)>0},即正向流集,其点集V即为所求!

2.图连通度K(G),定义K(G)为:K(G)=顶点数-1,G为双向完全图;K(G)=Min{P(a,b)},a,b不相邻,G为非双向完全图。

  • 构造流图D:将原图中的u,v分裂为两个等效顶点,以单位容量边相连,将原来的边映射为+无穷边
  • 求出不相邻点a到b的最大流,以及对应的割顶集S。
k连通图的基本性质这里略过。
下面实现一个基本连通图的k值以及割顶求法,测试数据如下:[实用P259页基本连通图]
7 12[顶点数,边数]
1 6
1 7
1 2
2 7
2 3
3 7
4 7
4 3
5 7
5 4
5 6
6 7
算法框架:
//转化图框架:有向图,无向图处理
//验证是否为完全图
//若非完全图,则枚举源点和目标点,结算最大流;
//若最大流比当前的最大值大,在用dfs求出最小割集,逻辑很清楚!
下面是代码实现:
#include <stdlib.h>
#include <assert.h>
#include <iostream>
#include <fstream>
using namespace std;
const int MAXN=30, MAXE=200;
//for flow graph
typedef struct Edge{
 int i, j, next, op, f, c;
};
Edge es[MAXE];
int eid=0, n, en, first[MAXN], pre[MAXN], ptr[MAXN], first1[MAXN], queue[MAXN], ansp[MAXN];
bool visited[MAXN];
//for orignal graph
bool map[MAXN][MAXN];
//for S set
bool ss[MAXN];
//declaration
void createGraph();
void addEdge(int i, int j, int c);
void Dicnic(int sv, int st);
void bfslevel(int sv, int st);
void dfs_maxflow(int sv, int st);
void dfsforS(int v);
//implementation
void createGraph(){
 ifstream in("input.txt");
 if(!in) exit(EXIT_FAILURE);
 cin.rdbuf(in.rdbuf());
 //read in for n, e
 cin>>n>>en;
 int x, y;
 //clr for all previous list
 eid=0, memset((void*)first, 0xff, sizeof(first)), memset((void*)map, 0, sizeof(map));
 for(int i=0; i<n; i++) addEdge(i, i+n, 1);//i -> i+n in weight of 1
 for(int i=0; i<en; i++){
  cin>>x>>y, map[x][y]=map[y][x]=true;
  addEdge(x+n, y, INT_MAX), addEdge(y+n, x, INT_MAX);
 }
 in.close();
}
void addEdge(int i, int j, int c){
 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++;
 es[eid].i=j, es[eid].j=i, es[eid].f=0, es[eid].c=-1;
 es[eid].next=first[j], first[j]=eid, es[eid].op=eid-1; eid++;//here:bugs,开始写成了后减,精力有点不集中!
}
//for Dicnic implementation
void Dicnic(int sv, int st){
 while(true){
  bfslevel(sv, st);
  if(pre[st]==INT_MAX) return;
  dfs_maxflow(sv, st);
 }
}
void bfslevel(int sv, int st){
 for(int i=0; i<2*n; i++) pre[i]=INT_MAX;
 int top=0, size=1; queue[0]=sv, pre[sv]=0;//here:bugs注意源点赋值
 while(top<size){
  int cn=queue[top++];//here!bugs队列的头处理
  if(cn==st) return;
  for(int e=first[cn]; e!=-1; e=es[e].next){
   if(es[e].c>es[e].f||(es[e].c==-1&&es[e].f>0)){
    if(pre[es[e].j]>pre[cn]+1){
     queue[size++]=es[e].j, pre[es[e].j]=pre[cn]+1;
    }
   }
  }
 }
}
void dfs_maxflow(int sv, int st){
 memcpy((void*)first1, (void*)first, sizeof(first));
 memset((void*)visited, 0, sizeof(visited));
 int top=0; queue[0]=sv;
 while(top>-1){
  if(queue[top]==st){
   int fmin=INT_MAX, value;
   for(int i=top; i>0; i–){
    if(es[ptr[queue[i]]].c>es[ptr[queue[i]]].f){
     if((value=es[ptr[queue[i]]].c-es[ptr[queue[i]]].f)<fmin) fmin=value;
    }
    if(es[ptr[queue[i]]].c==-1&&es[ptr[queue[i]]].f>0){
     if((value=es[ptr[queue[i]]].f)<fmin) fmin=value;
    }
   }
   //update the maxflow
   for(int i=top; i>0; i–){
    if(es[ptr[queue[i]]].c>es[ptr[queue[i]]].f)
     es[ptr[queue[i]]].f+=fmin, es[es[ptr[queue[i]]].op].f+=fmin;
    if(es[ptr[queue[i]]].c==-1&&es[ptr[queue[i]]].f>0)
     es[ptr[queue[i]]].f-=fmin, es[es[ptr[queue[i]]].op].f-=fmin;
   }
   return;
  }
  else{//dfs for maxflow
   int tp=queue[top], tmp=first1[tp];
   for(;tmp!=-1;tmp=es[tmp].next){
    if(!visited[es[tmp].j]){
     if((es[tmp].c>es[tmp].f||(es[tmp].c==-1&&es[tmp].f>0))&&pre[es[tmp].j]==pre[tp]+1){
      first1[tp]=es[tmp].next;
      queue[++top]=es[tmp].j, ptr[es[tmp].j]=tmp;
      break;
     }//if
    }//if
   }//for
   if(tmp==-1){visited[tp]=true; top–;}
  }
 }
}
void dfsforS(int v){
 ss[v]=true;
 for(int e=first[v]; e!=-1; e=es[e].next){//here:bugs
  if(!ss[es[e].j]&&
es[e].c>es[e].f) dfsforS(es[e].j);
 }
}
int _tmain(int argc, _TCHAR* argv[])
{
 createGraph();
 bool bf=true;
 for(int i=1; i<n; i++){
  for(int j=i+1; j<n; j++){
   assert(i!=j);
   if(!map[i][j]){bf=false; break;}
  }
  if(!bf) break;
 }
 if(bf){//bi-connected graph
  cout<<n-1<<endl;
  for(int i=0; i<n; i++) cout<<i<<" ";
  cout<<endl;
  goto jmp;
 }
 else{//for k-connected graph
  int ans=0;
  for(int vs=n; vs<2*n; vs++){
   for(int vt=0; vt<n; vt++){
    if(vs-n!=vt&&!map[vs-n][vt]){//maxflow for between vs and vt
     for(int i=0; i<eid; i++) es[i].f=0;
     Dicnic(vs, vt);
     int k=0;
     for(int i=first[vs]; i!=-1; i=es[i].next) k+=es[i].f;
     if(k>ans){
      ans=k;
      memset((void*)ss, 0, sizeof(ss));
      dfsforS(vs);
      int t=0;
      for(int i=0; i<n; i++)
       if(ss[i]&&!ss[i+n]) ansp[t++]=i;
     }//if
    }
   }
  }
  cout<<ans<<endl;
  for(int i=0; i<ans; i++) cout<<ansp[i]<<" ";
  cout<<endl;
 }
jmp:system("pause");
 return 0;
}
 
3.图的边连通度,类似于图顶点连通度;
K'(G),对于a,b顶点,从a到b的无公共编的轨,称为弱独立轨.其定义与K(G)是一致的。
通用构造算法如下:
  • 设在无向图中,将原有边e(u,v)映射为e’=(u, v), e”=(v,u),其容量均为1, 而有向图,则直接设置存在边容量为1。[这个和最大流模型是保持一致的]
  • 排除特殊的完全图情况,求出最大流,进而dfs求出在原图中的桥集
下面实现一个基本边连通图的k值以及桥集求法,测试数据如下:[实用P261页基本连通图]
5 6[顶点数,边数]
1 2
1 5
2 5
2 3
2 4
3 4
下面是完整代码实现:
#include <stdlib.h>
#include <assert.h>
#include <iostream>
#include <fstream>
using namespace std;
const int MAXN=40, MAXE=200;
typedef struct Edge{
 int i, j, next, op, c, f;
};
typedef struct Bridge{
 int i, j;
};
Edge es[MAXE];
Bridge bs[MAXE];
int eid=0, nv, ev, first[MAXN], first1[MAXN], pre[MAXN], ptr[MAXN], queue[MAXN];
bool visited[MAXN], ss[MAXN], map[MAXN][MAXN];
//declaration
void createGraph();
void addEdge(int i, int j, int c);
void Dicnic(int sv, int st);
void bfslevel(int sv, int st);
void dfs_maxflow(int sv, int st);
void dfsforS(int u);
//implementation
void createGraph(){
 ifstream in("input.txt");
 if(!in) exit(EXIT_FAILURE);
 cin.rdbuf(in.rdbuf());
 cin>>nv>>ev;
 int x, y;
 eid=0, memset((void*)first, 0xff, sizeof(first)), memset((void*)map, 0, sizeof(map));
 for(int i=0; i<ev; i++){
  cin>>x>>y, x–, y–;
  map[x][y]=map[y][x]=true, addEdge(x, y, 1), addEdge(y, x, 1);
 }
}
void addEdge(int i, int j, int c){
 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++;
 es[eid].i=j, es[eid].j=i, es[eid].f=0, es[eid].c=-1;
 es[eid].next=first[j], first[j]=eid, es[eid].op=eid-1; eid++;
}
void Dicnic(int sv, int st){
 while(true){
  bfslevel(sv, st);
  if(pre[st]==INT_MAX) return;
  dfs_maxflow(sv, st);
 }
}
void bfslevel(int sv, int st){
 for(int i=0; i<nv; i++) pre[i]=INT_MAX;
 int top=0, size=1; queue[0]=sv, pre[sv]=0;
 while(top<size){
  int cn=queue[top++];
  if(cn==st) return;
  for(int e=first[cn]; e!=-1; e=es[e].next){
   if((es[e].c>es[e].f||(es[e].c==-1&&es[e].f>0))&&pre[es[e].j]>pre[cn]+1)//here: bugs
    queue[size++]=es[e].j, pre[es[e].j]=pre[cn]+1;
  }
 }
}
void dfs_maxflow(int sv, int st){
 memcpy((void*)first1, (void*)first, sizeof(first));
 memset((void*)visited, 0, sizeof(visited));
 int top=0; queue[0]=sv;
 while(top>-1){
  if(queue[top]==st){
   int fmin=INT_MAX, value;
   for(int i=top; i>0; i–){
    if(es[ptr[queue[i]]].c>es[ptr[queue[i]]].f){
     if((value=es[ptr[queue[i]]].c-es[ptr[queue[i]]].f)<fmin) fmin=value;
    }
    if(es[ptr[queue[i]]].c==-1&&es[ptr[queue[i]]].f>0){
     if((value=es[ptr[queue[i]]].f)<fmin) fmin=value;
    }
   }
   for(int i=top; i>0; i–){
    if(es[ptr[queue[i]]].c>es[ptr[queue[i]]].f){
     es[ptr[queue[i]]].f+=fmin, es[es[ptr[queue[i]]].op].f+=fmin;
    }
    if(es[ptr[queue[i]]].c==-1&&es[ptr[queue[i]]].f>0){
     es[ptr[queue[i]]].f-=fmin, es[es[ptr[queue[i]]].op].f-=fmin;
    }
   }
   return;
  }
  else{//for first1 comparsion
   int tp=queue[top], tmp=first1[tp];
   for(;tmp!=-1;tmp=es[tmp].next){
    if(!visited[es[tmp].j])
     if((es[tmp].c>es[tmp].f||(es[tmp].c==-1&&es[tmp].f>0))&&pre[es[tmp].j]==pre[tp]+1){
      queue[++top]=es[tmp].j, ptr[es[tmp].j]=tmp;
      break;
     }
   }//for
   if(tmp==-1){visited[tp]=true; top–;}
  }
 }
}
void dfsforS(int u){
 ss[u]=true;
 for(int e=first[u]; e!=-1; e=es[e].next){
  if(!ss[es[e].j]&&es[e].c>es[e].f) dfsforS(es[e].j);
 }
}
int _tmain(int argc, _TCHAR* argv[])
{
 createGraph();
 bool bf=true;
 for(int i=0; i<nv; i++){
  for(int j=i+1; j<nv; j++){
   if(!map[i][j]){bf=false; break;}
  }
 }
 if(bf){//full-connencted
  cout<<nv-1<<endl;
  for(int i=1; i<nv; i++) cout<<"0 "<<i<<endl;
  goto jmp;
 }
 else{//for the intialization of edages
  int ans=0;
  for(int s=0; s<nv; s++){
   for(int t=0; t<nv; t++){
    if(s!=t&&!map[s][t]){//find non-adjancent two vertexs
     for(int i=0; i<eid; i++) es[i].f=0;
     Dicnic(s, t);
     int k=0;
     for(int e=first[s]; e!=-1; e=es[e].next) k+=es[e].f;
     if(k>ans){//find the according bridge
      ans=k;
      memset((void*)ss, 0, sizeof(ss));
      dfsforS(s); int t=0;
      for(int i=0; i<nv; i++){
       for(int j=0; j<nv; j++){
        if(ss[i]&&!ss[j]&&map[i][j]) bs[t].i=i, bs[t++].j=j;
       }
      }
     }//if
    }//if
   }//for vt
  }//for vs
  cout<<ans<<endl;
  for(int i=0; i<ans; i++) cout<<bs[i].i<<" "<<bs[i].j<<endl;
 }
jmp:system("pause");
 return 0;
}
 
4.多源多汇网络的可行流计算
这类型题目在算导中有所提及,思路是对于多个源点加入一个pre-source,对于多个目标,加入一个post-dest,这样模型就统一到了熟悉的模型之上。
引用《实用》上的例题来实现一个具体例子。
 
商品供应系统问题:
如图商品供应系统,边的方向表示商品流向,边上的数字表示商品从某地到某地的最大通过能力。商品的货源来自于x1,x2和x3,其中x1的供应量为5,x2为10,x3为5。这些商品在商场y1,y2和y3出售。y1的需求为5,y2为10,y3为5。是否能同时满足?

输入数据:
10 9
1 4 3
1 5 3
2 1 7
2 5 4
2 3 9
3 5 3
3 7 7
4 8 8
4 6 3
5 4 2
5 6 8
6 8 1
6 9 2
6 10 4
7 5 1
7 6 6
7 10 8
8 9 2
10 9 7
3 1 5 2 10 3 5
3 8 5 9 10 10 5
 
5.容量下界的网络流计算
这个算法看起太奇特了,难度完全在图的转化上,首先是将上下界分离为必要弧和增量弧,然后加入x,y的源点和汇点,再进行改造;算法首先从x,y出发找到一个对改造网络的必要弧饱和处理方案,然后再对残留网络进行扩展!说的自己都有点晕了,画了个转化图发现今天思维迟钝的不可理解,算了,暂时放一下。遇到思维短路期了!
 
6.最小费用最大流 网上的两种思路
这个问题再短路就简直不可原谅了。
  • Ford-Fulkerson增广最短路算法[Successive Shortest Path]:在最大流系统中加入单位流量的费用因子,然后求在最小费用基础上的最大流,输出为总的输送费用B(F)=Sum(Bij*Fij).这个思路挺典型的,感觉有点不像是最大流,倒像是最短路+增量算法的问题。
引用别人的论述:把各条弧上单位流量的费用看成某种长度,用求解最短路问题的方法确定一条自V1至Vn的最短路;在将这条最短路作为可扩充路,用求解最大流问题的方法将其上的流量增至最大可能值;而这条最短路上的流量增加后,其上各条弧的单位流量的费用要重新确定,如此多次迭代,最终得到最小费用最大流.
算法描述:
  • 对于G求出其从S到T的最短路[Bellman-Ford],初始时F=0。
  • 在F(k-1)基础上进行流增量,实际上是求出可达最短路上的瓶颈流量。尤其最短路时已经求出了累积的最小费用,直接用l[t]*瓶颈流量即可。

代码框架:[实用上的框架]

Successive Shortest Path

1    Establish a feasible flow x when F=0
2    while ( Gx contains any shortest path in F(k-1) ) do
3        find the shortest path from s to t
4       
5        add the cost from the shortest path from s to t in l[t] 
6        find the bottleneck of flow(k-1) and the sum of cost is l[t]*|bottleneck|

  • 消圈算法[Cycle Canceling]:网络G的最大流是G的一个最小费用流的充要条件是,最大流的残图中不含负费用圈

伪代码框架:[引自 Zealint ‘s Minimum Cost Flow, Part 2: Algorithms ]

 Cycle-Canceling

1    Establish a feasible flow x in the network
2    while ( Gx contains a negative cycle ) do
3        identify a negative cycle W
4       
5        augment  units of flow along the cycle W
6        update Gx

一个练手的基本题目:在如下图中,求出其最小费用最大流。

测试数据:
5 7
0 1 10 4
0 2 8 1
2 1 5 2
1 3 2 6
2 3 10 3
1 4 7 1
3 4 4 2
 
  • Cycle cancel算法实现:实用的模型确实很强,那种模型的处理,使得正流和负流统一起来了!然后沿正向流的增加[残图中g的增加]和负流的处理都一致料。呵呵,最后的费用流只需要把正向流的集合跑一次即可!来分析下算法复杂度:Bellman-Ford的负圈测试O(VE),每条边的容量上限M,费用上限为C,因此最大流的费用为mCM,统一之复杂度为O(E^2VCM).

代码实现:[可用为模板]

#include <iostream>
#include <fstream>

using namespace std;

//Cycle-canceling Algorithm
//Code Skeleton
//1    Establish a feasible flow x in the network
//2    while ( Gx contains a negative cycle ) do
//3        identify a negative cycle W
//4       
//5        augment  units of flow along the cycle W
//6        update Gx

//declaration
typedef struct Edge{
 int i, j, f, c, w, op, next;//using uniform Edge presetation
};
const int MAXN=20, MAXE=400;
Edge es[MAXE];
int eid=0, first[MAXN], hv[MAXN], ev[MAXN], l[MAXN], w[MAXN], pre[MAXN], ptr[MAXN];//for bellman-ford loop
int nv, ne;

//declaration
void createGraph();
void addEdge(int start, int end, int cap, int cost);

//maxflow algorithm
void highpreflow();
void initialize();
void discharge(int u);
bool relabel(int u);
bool push(int eid);

//implementation
void createGraph(){
 ifstream in("input.txt");
 if(!in) exit(EXIT_FAILURE);
 cin.rdbuf(in.rdbuf());
 //read in data and establish the graph
 cin>>nv>>ne; eid=0, memset((void*)first, 0xff, sizeof(first));
 int start, end, cap, cost;
 for(int i=0; i<ne; i++)
  cin>>start>>end>>cap>>cost, addEdge(start, end, cap, cost);
}

void addEdge(int start, int end, int cap, int cost){
 if(!cap) return;
 es[eid].i=start, es[eid].j=end, es[eid].f=0, es[eid].c=cap, es[eid].w=cost;
 es[eid].next=first[start], first[start]=eid, es[eid].op=eid+1; eid++;
 es[eid].i=end, es[eid].j=start, es[eid].f=0, es[eid].c=-1, es[eid].w=-cost;
 es[eid].next=first[end], first[end]=eid, es[eid].op=eid-1; eid++;
}

void highpreflow(){
 initialize();
 int pos=0, u=l[pos];
 while(u!=-1){
  int oldh=hv[u];
  discharge(u);
  if(oldh!=hv[u]){
   if(pos!=0) l[pos]^=l[0], l[0]^=l[pos], l[pos]^=l[0];
   pos=0;
  }
  u=l[++pos];
 }
}

void initialize(){
 memset((void*)hv, 0, sizeof(hv)), memset((void*)ev, 0, sizeof(ev));
 memset((void*)l, 0xff, sizeof(l));
 for(int i=0; i<nv-2; i++) l[i]=i+1;
 hv[0]=nv-1;
 for(int i=first[0]; i!=-1; i=es[i].next){
  if(es[i].c>0){
   es[i].f+=es[i].c, es[es[i].op].f+=es[i].c;
   ev[es[i].j]+=es[i].c, ev[0]-=es[i].c;
  }
 }
}

bool relabel(int u){
 if(ev[u]<=0) return false;
 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)){
   if(hv[es[e].j]<hv[u]) minV=false;
   if(hv[es[e].j]<hmin) hmin=hv[es[e].j];
  }
 }
 if(minV&&hmin<=nv){hv[u]=hmin+1; return true;}
 return false;
}

bool push(int eid){//es[eid].i->es[eid].j
 if(ev[es[eid].i]<=0||hv[es[eid].i]!=hv[es[eid].j]+1) return false;
 int dt;
 if(es[eid].c>es[eid].f){
  dt=min(ev[es[eid].i], es[eid].c-es[eid].f);
  es[eid].f+=dt, es[es[eid].op].f+=dt;
  ev[es[eid].i]-=dt, ev[es[eid].j]+=dt;
  return true;
 }
 if(es[eid].c==-1&&es[eid].f>0){
  dt=min(ev[es[eid].i], es[eid].f);
  es[eid].f-=dt, es[es[eid].op].f-=dt;
  ev[es[eid].i]-=dt, ev[es[eid].j]+=dt;
  return true;
 }
 return false;
}

void discharge(int u){
 int cur=first[u];
 while(ev[u]>0){
  if(cur==-1) relabel(u), cur=first[u];
  else if((es[cur].c>es[cur].f||(es[cur].c==-1&&es[cur].f>0))&&hv[u]==hv[es[cur].j]+1)
   push(cur);
  else cur=es[cur].next;
 }
}

int _tmain(int argc, _TCHAR* argv[])
{
 createGraph();
 highpreflow();

 //cycle cancel
 bool cycle=false;
 do{//cycle cancel logic
  w[0]=0, memset((void*)pre, 0xff, sizeof(pre));
  for(int i=1; i<nv; i++) w[i]=INT_MAX; cycle=false;
  int start=-1, fmin=INT_MAX;
  for(int i=1; i<nv; i++){
   for(int e=0; e<eid; e++){
    if(es[e].c>es[e].f||(es[e].c==-1&&es[e].f>0))//in the residental graph
     if(w[es[e].i]!=INT_MAX&&w[es[e].i]+es[e].w<w[es[e].j]) w[es[e].j]=w[es[e].i]+es[e].w, pre[es[e].j]=es[e].i, ptr[es[e].j]=e;
   }
  }

  for(int i=1; i<nv; i++){
   for(int e=0; e<eid; e++){
    if(es[e].c>es[e].f||(es[e].c==-1&&es[e].f>0))//in the residental graph
     if(w[es[e].i]!=INT_MAX&&w[es[e].i]+es[e].w<w[es[e].j]){ start=es[e].j, cycle=true; break;}
   }//Bellman-Ford一行不差的!
   if(cycle) break;//existing one minus cycle
  }
  if(!cycle) break;//no-minus cycle in the existing system
  //here: if self-loop? ignore this case
  int nxt=pre[start], value;
  do{
   if(es[ptr[nxt]].c>es[ptr[nxt]].f){//here: w’s value
    if((value=es[ptr[nxt]].c-es[ptr[nxt]].f)<fmin) fmin=value;
   }
   if(es[ptr[nxt]].c==-1&&es[ptr[nxt]].f>0){
    if((value=es[ptr[nxt]].f)<fmin) fmin=value;
   }//please check
  }while(nxt!=pre[start]);
  //update the minus cycle
  nxt=pre[start];
  do{//bugs : in the residental graph, decreas the flow on this direction, increase the opposite direction
   if(es[ptr[nxt]].c>es[ptr[nxt]].f)
    es[ptr[nxt]].f+=fmin, es[es[ptr[nxt]].op].f+=fmin;
   else if(es[ptr[nxt]].c==-1&&es[ptr[nxt]].f>0)
    es[ptr[nxt]].f-=fmin, es[es[ptr[nxt]].op].f-=fmin;
   /*assert(es[ptr[nxt]].f>=0&&es[es[ptr[nxt]].op].f>=0);*/
   nxt=pre[nxt];
  }while(nxt!=pre[start]);//这个地方有点搞,呵呵!闪了一下,证明:存在圈那么从start开始一定有一个出,一个入,OK,用pre验证即可。
 }while(cycle);

//MIT上说要再走一次dfs来看是否确实无圈!
 //find the minmal cost flow along the forward-flow
 int forwardflow=0;
 for(int i=0; i<eid; i++){
  if(es[i].c>0) forwardflow+=es[i].f*es[i].w;
 }
 cout<<forwardflow<<endl;
 return 0;
}

  • Successive Shortest Path算法实现:每次找出更新流后的最小费用路径,找出瓶颈流以及用w[st]表示其最短路径的费用长度,累计即是最小费用。算法复杂度:Bellman-Ford的负圈测试O(VE),每条边的容量上限M,费用上限为C,因此每次找最小路径O(S(m,n,C)),统一之复杂度为O(MS(m,n,C)).

代码实现:[可用为模板]

#include <iostream>
#include <fstream>

using namespace std;

/* template from Top coder, implementation refer to practical alogrithm.
Successive Shortest Path
1    Transform network G by adding source and sink
2    Initial flow x is zero
3    while ( Gx contains a path from s to t ) do
4        Find any shortest path P from s to t
5        Augment current flow x along P
6        update Gx
*/

const int MAXN=20, MAXE=400;
typedef struct Edge{
 int i, j, next, op, f, c, w;
}Edge;
Edge es[MAXE];
int eid=0, first[MAXN], w[MAXN],/*accumulated value*/ pre[MAXN], ptr[MAXN];
int nv, ne;

//declaration
void addEdge(int i, int j, int c, int w);
int expandPath(int sv, int st);
void createGraph();

//implementation
void addEdge(int i, int j, int c, int w){
 if(!c) return;
 es[eid].i=i, es[eid].j=j, es[eid].c=c, es[eid].w=w, es[eid].f=0;
 es[eid].next=first[i], first[i]=eid, es[eid].op=eid+1; eid++;
 es[eid].i=j, es[eid].j=i, es[eid].c=-1, es[eid].w=-w, es[eid].f=0;
 es[eid].next=first[j], first[j]=eid, es[eid].op=eid-1; eid++;
}

void createGraph(){
 ifstream in("input.txt");
 if(!in) exit(EXIT_FAILURE);
 cin.rdbuf(in.rdbuf());
 cin>>nv>>ne;eid=0, memset((void*)first, 0xff, sizeof(first));
 int start, end, cap, costw;
 for(int i=0; i<ne; i++)
  cin>>start>>end>>cap>>costw, addEdge(start, end, cap, costw);
}

int expandPath(int sv, int st){
 memset((void*)pre, 0xff, sizeof(int)*nv);
 for(int i=0; i<nv; i++) w[i]=INT_MAX;
 pre[sv]=sv,w[sv]=0; bool change=false;
 do{
  change=false;
  for(int i=1; i<nv; i++){
   for(int e=0; e<eid; e++){//flow may be changed during process
    if(pre[es[e].i]!=-1){
     if(es[e].c>es[e].f)
      if(w[es[e].i]+es[e].w<w[es[e].j]) w[es[e].j]=w[es[e].i]+es[e].w, pre[es[e].j]=es[e].i, ptr[es[e].j]=e, change=true;
     if(es[e].c==-1&&es[e].f>0)
      if(w[es[e].i]+es[e].w<w[es[e].j]) w[es[e].j]=w[es[e].i]+es[e].w, pre[es[e].j]=es[e].i, ptr[es[e].j]=e, change=true;
    }
   }
  }
 }while(change);//if change then we continue change
 //if we can’t from sv to st;
 if(pre[st]==-1) return 0;
 int i=st, a=INT_MAX, value;
 for(;i!=sv;i=pre[i]){
  if(es[ptr[i]].c>es[ptr[i]].f){//here:bugs i->ptr[i]
   if((value=es[ptr[i]].c-es[ptr[i]].f)<a) a=value;
  }
  if(es[ptr[i]].c==-1&&es[ptr[i]].f>0){
   if((value=es[ptr[i]].f)<a) a=value;
  }

 }
 return a;
}

int _tmain(int argc, _TCHAR* argv[])
{
 createGraph();
 int a=expandPath(0, nv-1), aflow=0, sv=0, st=nv-1;
 while(a){
  for(int i=st;i!=sv;i=pre[i]){//change the flow
   if(es[ptr[i]].c>es[ptr[i]].f) es[ptr[i]].f+=a, es[es[ptr[i]].op].f+=a;
   if(es[ptr[i]].c==-1&&es[ptr[i]].f>0) es[ptr[i]].f-=a, es[es[ptr[i]].op].f-=a;
  }
  aflow+=w[st]*a;
  a=expandPath(0, nv-1);
 }
 cout<<aflow<<endl;
 return 0;
}

Advertisements