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