萌新EK,WA28分求助

P3376 【模板】网络最大流

Into_qwq @ 2020-08-05 17:21:19

RT,求大佬们抽出少许时间帮助我这只蒟蒻/kel

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500010;
const ll inf=2005020000;
int n,m,s,t,u,v,book[3000][3000],pre[N],head[N],cnt=1;
bool vis[N];
ll w,ans,dis[N];
queue <int> q; 
struct edge{
    int to,nex;
    ll val;
}e[N];
inline void add(int a,int b,ll c){
    e[++cnt].to=b;
    e[cnt].val=w;
    e[cnt].nex=head[a];
    head[a]=cnt;
}
inline bool bfs(){
    memset(vis,0,sizeof(vis));
    while(q.size()) q.pop();
    q.push(s);vis[s]=1;
    dis[s]=inf;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=e[i].nex){
            if(!e[i].val) continue;
            int to=e[i].to;
            if(vis[to]) continue;
            dis[to]=min(dis[x],e[i].val);pre[to]=i;
            vis[to]=1;q.push(to);
            if(to==t) return 1;
        }
    }
    return 0;
}
inline void update(){
    int a=t;
    while(a!=s){
        int b=pre[a];
        e[b].val-=dis[t];
        e[b^1].val+=dis[t];
        a=e[b^1].to;
    }
    ans+=dis[t];
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    while(m--){
        cin>>u>>v>>w;
        if(!book[u][v]) add(u,v,w),add(v,u,0),book[u][v]=cnt;
        else e[book[u][v]-1].val+=w;
    }
    while(1)
        if(bfs()) update();
        else break;
    printf("%lld\n",ans);
    return 0;
}

record:https://www.luogu.com.cn/record/36378093


by Prean @ 2020-08-05 17:27:21

EK爬爬爬,这道题还卡EK

基本上所有网络流题都卡EK


by FunnyCreatress @ 2020-08-05 17:34:34

inline void add(int a,int b,ll c){
    e[++cnt].to=b;
    e[cnt].val=w;//???
    e[cnt].nex=head[a];
    head[a]=cnt;
}

你反向边建了个寂寞


by FunnyCreatress @ 2020-08-05 17:34:43

@IamnotTXN


by Into_qwq @ 2020-08-05 17:38:58

谢谢


by Into_qwq @ 2020-08-05 17:39:30

我好想忘记该参数了(不过怎么AC了这么多点)


by Prean @ 2020-08-05 17:42:38

@FunnyCreatress 他主函数建了反向边。。。


by Into_qwq @ 2020-08-05 17:44:47

是我传参出了问题/kk


by Into_qwq @ 2020-08-05 17:47:06

@FunnyCreatress AC了,谢谢大佬orz


by FunnyCreatress @ 2020-08-05 17:54:55

@limaopipi2022 不是建了寂寞,他反向边建了一条容量为 w 的反向边


by 聪明的猪 @ 2020-10-27 20:43:17

话说回来,EK建边最好还是用邻接矩阵好一点(毕竟邻接矩阵存不下的图EK肯定也跑不动x)


|