萌新 EK算法 44pt 求修改

P3376 【模板】网络最大流

Sky_Walker @ 2024-06-30 16:24:54

本人普及组小白一枚,最近看了网络流的一些算法,想拿模板练练手。但测试4、5、8 WA了;6、7、9、10 TLE。求大佬指正,是我对FF和EK的理解有误吗?

#include <stdio.h>
#define N 250
// #include <Windows.h>
#define int long long

int min(int a,int b){
    return a>b?b:a;
}

int bfs(int c[N][N],int n,int s,int t){
    int queue[N][3]={0};
    int visited[50]={0};
    int head,tail,i,u,v,ui,vi,f,flag;
    head=0;
    tail=0;
    queue[0][0]=s;//记录当前位置节点
    queue[0][1]=0;//记录上一个节点的坐标
    queue[0][2]=2147483648;//记录当前的最大容许流量
    visited[s]=1;//记录是否有被访问

    flag=0;//记录是否达到汇点
    while(head<=tail){
        u=queue[head][0];
        for (i=1;i<=n;i++){
            if (c[u][i]>0 && (!visited[i])){//未访问且容量大于0入队
                tail++;
                queue[tail][0]=i;//新节点i
                queue[tail][1]=head;//i节点上一个节点u的指标为head
                queue[tail][2]=min(queue[head][2],c[u][i]);//新节点i最大容许流量为u到i的容量和u节点最大容量的最小值
                visited[i]=1;
                // printf("%d %d %d\n",queue[tail][0],queue[queue[tail][1]][0],queue[tail][2]);
                if (i==t){
                flag=1;//到达汇点退出
                break;
            }
            }

        }
        if (flag)break;
        head++;
    }
    // printf("%d\n",flag);
    if (!flag) return 0;//未达汇点结束
    f=queue[tail][2];
    vi=tail;
    while(queue[vi][0]!=s){//根据父节点指标依次更新残余网络
        // printf("a%d\n",queue[vi][0]);
        ui=queue[vi][1];
        u=queue[ui][0];
        v=queue[vi][0];
        c[u][v]-=f;//当前边
        c[v][u]+=f;//反向边
        vi=ui;
    }

    return f;
}

int main(){
    int n,m,s,t,i,u,v,j,f,aug;
    int c[N][N]={0};
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (i=0;i<m;i++){
        scanf("%d%d",&u,&v);
        scanf("%d",&(c[u][v]));
    }

    f=0;//最大容量
    do{
        // printf("\n");
        aug=bfs(c,n,s,t);//增广
        f+=aug;

        // for (i=1;i<=n;i++){
        //     for (j=1;j<=n;j++)printf("%d ",c[i][j]);
        //     printf("\n");
        // }
        // printf("%d\n",aug);
        // int a;
        // Sleep(200);
        // scanf("%d",&a);

    }
    while(aug>0);

    //printf("\n");
    printf("%d ",f);
    return 0;
}

by 执着之幻 @ 2024-07-25 09:29:27

建议先学一下新的存图方法,否则你上面的做法一定会超时 @ Sky_Walker


by 执着之幻 @ 2024-07-25 09:29:39

@Sky_Walker


|