夜光WAN @ 2021-08-02 18:09:42
请问为什么EK算法用链式前向星存图时没有加反向边，用bfs找到增广路后只对路上的流量缩减（未同时增加反向边流量）为什么能AC？不止这题能AC。
by RenaMoe @ 2021-08-02 18:23:12
by 听取MLE声一片 @ 2021-08-02 18:44:47
我大为震撼
by 听取MLE声一片 @ 2021-08-02 18:47:41
费用流就挂了
by hhoppitree @ 2021-08-02 19:10:41
兄啊你是不是在做 FJOI，我从来不知道网络流要加反向边
by zjrdmd @ 2021-08-03 16:54:13
@夜光WAN 给个代码
by 夜光WAN @ 2021-08-03 17:01:56
@LD_ZJR_FG
#include<stdio.h>
#include<string.h>
#define ll long long
#define inf 9999999999
#define N 205
ll flow[N][N],rec[N];
int queue[N],pre[N];
struct{
int v,next;
}edge[N*N];
int head[N],cnt;
void add(int u,int v){
edge[++cnt].v=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
ll min(ll a,ll b){
return a<b?a:b;
}
int n,m,s,t;
int bfs(){
int first=0,last=0,i;
memset(rec,0,sizeof(rec));
memset(pre,0,sizeof(pre));
rec[s]=inf;
queue[last++]=s;
while(first<last){
int now=queue[first++];
for(i=head[now];i;i=edge[i].next){
int v=edge[i].v;
if(!pre[v]&&flow[now][v]){
rec[v]=min(rec[now],flow[now][v]);
queue[last++]=v;
pre[v]=now;
}
}
}
return pre[t];
}
ll EK(){
ll sumflow=0;
int i;
while(bfs()){
for(i=t;i!=s;i=pre[i]){
flow[pre[i]][i]-=rec[t];
//flow[i][pre[i]]+=rec[t];
}
sumflow+=rec[t];
}
return sumflow;
}
int main(){
int u,v,w;
scanf("%d%d%d%d",&n,&m,&s,&t);
while(m--){
scanf("%d%d%d",&u,&v,&w);
flow[u][v]+=w;
add(u,v);
}
printf("%lld",EK());
}by 夜光WAN @ 2021-08-03 17:03:33
@hhoppitree 但是我在网上看的EK算法的帖子都有说要加入反向边，要给找到的增广路一个“反悔”的机会？
by hjxhjx @ 2021-09-20 21:13:50
我也没加反向边，也过了...但是同样的代码交B3606就会挂掉
希望管理员可以加几组更强的数据qwq