sap 网络流
SAP算法框架：1、定义距离标号为各点到汇点距离的下界(即最短距离)。
2、在初始距离标号的基础上，不断沿着可行弧找增广路。
3、遍历当前节点完以后，为了保证下次再来的时候有路可走，重新标号当前距离。
4、检查重新标记的顶点，若其为原点，且被标记的高度等于节点个数时，图中已经不存在增广路，算法可结束。否则继续从原点开始遍历。
由于我们不停的遍历，最大流很可能便早就已经求出来了。那么我们接下来的遍历便成了无用功。可以发现，距离标号是连续单调变化的。如果某一种大小标号的节点数量为零。也就是出现了不连续，断层！那么图中也不肯能再存在增广路了。实践中，我们用一个vh[ i ]数组用来记录标号为i的顶点的个数，若重标号使得vh数组中的原标号数目变为了0，那么就停止算法。
View Code
int find(int u,int FLOW) //FLOW是总流量
{
if(T==u)
return FLOW;
int left=FLOW; //left是剩余流量
int f;
int temp=n-1;
for(node *p=link;p;p=p->next)
{
int res=p->f-flow; //计算该边剩余的可行流量
if(res && h==h+1)//满足可行弧条件
{
int MIN=min(res,left);//计算最小可行流量
f=find(p->v,MIN);//递归寻找增广路
left-=f;
flow+=f;
flow-=f;
if(!left || h==n)
return FLOW-left; //总流量减去剩下的流量=流去的流量
}
res=p->f-flow;
if(res && h<temp)
temp=h;
}
if(left==FLOW) //需要重新标记
{
vh]--;//重标记以后，原标记的数目肯定减少了一
if(!vh]) //出现了断层，已经找到了最大流，停止算法
{
h=n;
}
else
{
h=temp+1;
vh]++;
}
}
return FLOW-left;
}
void sap()
{
int ans=0;
n=T+1; //S->T 有T+1个点
memset(vh,0,sizeof(vh));//常数优化数组
memset(h,0,sizeof(h));
memset(flow,0,sizeof(flow));
vh=n;//标号为0的顶点有n个
while(h<n)
{
ans+=find(S,inf);
}
cout<<ans<<endl;
}
页:
[1]