求助大佬。8-10样例没过,能不能提供一下样例或者解决方案

P3376 【模板】网络最大流

227737329rrr @ 2023-06-01 18:44:53

//n个点,m条边,源点编号1,汇点编号n
#include<bits/stdc++.h> 
using namespace std;

long long Source,Collect;//源点、汇点 
long long N;//图的点数 
long long**cap;//容量 
long long**flow;//流量 

long long*Ceng_ISAP;//Ceng_ISAP[i]: 访问i需要进过的最小的路径, 层次结构 
long long*cur;//当前弧,用于弧优化 
long long*gap;//gap优化,gap[i]表示i层的结点个数 

//与Dinic算法不同的是,ISAP是从汇点往源点构建层次的 
long long BFS_ISAP(){
    //初始化层次数组
    for(long long i=0;i<N;i++){
        Ceng_ISAP[i]=N;
    }
    Ceng_ISAP[Collect]=0;
    queue<long long> que;
    que.push(Collect);//将汇点加入队列
    while(!que.empty()){
        long long temp=que.front();
        que.pop();
        gap[Ceng_ISAP[temp]]++;
        //遍历temp的所有出边 
        for(long long i=0;i<N;i++){ 
            //如果边的剩余容量大于0且终点未访问过
            if(Ceng_ISAP[i]==N&&cap[i][temp]-flow[i][temp]>0){ 
                Ceng_ISAP[i]=Ceng_ISAP[temp]+1;//更新终点的层次
                que.push(i);
            }
        }
    }
    return Ceng_ISAP[Source]<N; 
}

long long DFS_ISAP(long long now_p,long long limit)
{
    //如果当前节点是汇点,返回当前DFS通路最大的流量limit 
    if(now_p==Collect) return limit;
    long long cost=0;//流量limit已经消耗的消耗的流量cost,即增广量 
    //从当前弧开始遍历now_p的所有出边
    for(long long i=cur[now_p];i<N;i++){
        cur[now_p]=i;//更新当前弧
        //如果边的容量大于0且终点的层次比当前节点小1
        if(Ceng_ISAP[now_p]==Ceng_ISAP[i]+1&&cap[now_p][i]-flow[now_p][i]>0){ 
            long long temp=DFS_ISAP(i,min(limit-cost,cap[now_p][i]-flow[now_p][i]));//递归寻找增广路并返回增广量 
            //如果增广成功 
            if(temp>0){
                flow[now_p][i]+=temp;//更新正向边的流量
                flow[i][now_p]-=temp;//更新反向边的流量
                cost+=temp;//累加增广流量
                if(limit==cost) return cost;//如果流量限制已经达到,退出循环
            }
        }
    }
    //if(cost==0){ //如果当前节点无法继续增广
        gap[Ceng_ISAP[now_p]]--; //更新 gap 数组
        if(gap[Ceng_ISAP[now_p]]==0){
            Ceng_ISAP[Source]=N; //如果当前高度没有节点,则更新源点高度为 N
        }
        long long minn=N-1; //记录当前节点能够到达的最小高度
        for(long long i=0;i<N;i++){ //遍历当前节点的所有出边
            if(cap[now_p][i]-flow[now_p][i]>0) minn=min(minn,Ceng_ISAP[i]); // 更新最小高度
        }
        Ceng_ISAP[now_p]=minn+1; //更新当前节点的高度标签
        gap[Ceng_ISAP[now_p]]++; //更新 gap 数组
        cur[now_p]=0; // 重置当前弧
    //}
    return cost;//返回增广流量
}

long long ISAP()
{
    long long ret=0;
    Ceng_ISAP=new long long[N];
    cur=new long long[N];
    gap=new long long[N+1];
    BFS_ISAP();
    while(Ceng_ISAP[Source]<N){
        for(long long i=0;i<N;i++){
            cur[i]=0;
        }
        ret+=DFS_ISAP(Source,INT_MAX);
    }
    delete[]Ceng_ISAP;
    delete[]cur;
    delete[]gap;
    return ret;
}

void CreatMapp();
void DeleteMemory();

int main ()
{
    CreatMapp();
    cout<<ISAP()<<endl;
    DeleteMemory(); 
}

//根据参数初始化图和变量 
void CreatMapp(){
    cin>>N;
    long long m;
    cin>>m;
    cin>>Source;Source--;
    cin>>Collect;Collect--;
    cap=new long long*[N];
    flow=new long long*[N];
    for(long long i=0;i<N;i++){
        cap[i]=new long long[N];
        flow[i]=new long long[N];
        for(long long j=0;j<N;j++){
            cap[i][j]=flow[i][j]=0;
        }
    }
    for(long long i=0;i<m;i++){
        long long u,v,c;
        cin>>u>>v>>c;
        cap[u-1][v-1]=+c;
    }
//  cout<<"N:"<<N<<" Source:"<<Source<<" Collect:"<<Collect<<endl;
//  for(long long i=0;i<N;i++){
//      for(long long j=0;j<N;j++){
//          cout<<"("<<i<<","<<j<<"):"<<cap[i][j]<<" ";
//      }
//      cout<<endl;
//  }
}
//清除动态分配的空间 
void DeleteMemory(){
    for(long long i=0;i<N;i++){
        delete[]cap[i];
        delete[]flow[i];
    }
    delete[]cap;
    delete[]flow;
} 

by toolazy @ 2023-10-12 22:27:35

同问


by kabout @ 2024-04-09 19:57:48

同问


|