general-bfs.cpp

这是关于图论算法里面的一些代码,图论基本的思想代码的实现

/*一般的宽搜找增广路，没有任何的改进，易受流量的限制，效率不高，但也可以在PKU上过很多题
 */
const int MaxVertex = 410;   //最大节点数
int c[MaxVertex][MaxVertex];
int f[MaxVertex][MaxVertex];
 
int fordfulkson()
{
    int front,rear,now,i,tmp;
    memset(pre,0xff,sizeof(pre)); //记录前驱节点
    front=rear=0;
    que[rear++]=0;
    pre[0]=0;
    while(front<rear){
        now=que[front++];
        for(i=1;i<=n;i++){
            if(pre[i]==-1){
                if(f[now][i]<c[now][i]){ //还有容量可供扩充，正向弧
                    que[rear++]=i;
                    pre[i]=now;tmp=c[now][i]-f[now][i];
                }
                if(f[i][now]>0){ //残留网的构建 ，反向弧
                    que[rear++]=i;
                    pre[i]=now+n;
                }  if(pre[n]!=-1)return 1;
            }
				}
    }
    return 0;
}
int findmin()
{
    int i,tmp,t,value;
    value=INF;i=n;
    while(i!=0){
        tmp=pre[i];
        if(tmp>n){//反向弧
            tmp-=n;
            value=value<f[i][tmp]?value:f[i][tmp];
        }
        else{//正向弧
            t=c[tmp][i]-f[tmp][i];
            value=t<value?t:value;
        }
        i=tmp;
    }
    return value;
}

int maxflow()
{
    int i,tmp,value;
    memset(f,0,sizeof(f));
    while(fordfulkson()){
        value=findmin();
        i=n;
        while(i!=0){//沿增广路增加流
            tmp=pre[i];
            if(tmp>n){
                tmp-=n;
                f[i][tmp]-=value;
            }
            else {
                f[tmp][i]+=value;
            }
            i=tmp;
        }
    }
    for(tmp=0,i=1;i<n;i++)tmp+=f[0][i];
    return tmp;
}