为什么爆零

P3376 【模板】网络最大流

Mr_ll @ 2021-10-27 17:02:26

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
const int N=10010,M=200010;
int n,m,s,t,u,v;
ll ans,yu[N],cnt=1,w,h[N],dep[N];
struct qwe{
    int to,net;
}tr[M];
void add(int x,int y,ll z){
    tr[++cnt].to=y;
    yu[cnt]=z;
    tr[cnt].net=h[x];
    h[x]=cnt;
}
bool ff(){
    queue<int> q;
    memset(dep,0,(n+1)*sizeof(int));
    dep[s]=1;
    q.push(s);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=h[x];i;i=tr[i].net){
            int y=tr[i].to;
            if(yu[i]&&!dep[y]){
                dep[y]=dep[x]+1;
                q.push(y);
            }
        }
    }
    return dep[t];
}
ll dfs(int u,ll in){
    if(u==t) return in;
    ll out=0;
    for(int i=h[u];i&&in;i=tr[i].net){
        int v=tr[i].to;
        if(yu[i]&&dep[v]==dep[u]+1){
            ll res=dfs(v,min(in,yu[i]));
            yu[i]-=res;
            yu[i^1]+=res;
            in-=res;
            out+=res;
        }
    }
    if(out==0) dep[u]=0;
    return out;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        scanf("%d%d%lld",&u,&v,&w);
        add(u,v,w);
        add(v,u,0);
    }
    while(ff())
    ans+=dfs(s,1e18);
    printf("%lld\n",ans);
    return 0;
}

by Vaino @ 2021-10-27 17:03:00

因为我这个菜鸡坐你旁边导致你变成菜鸡


by Zwaire @ 2021-10-30 06:43:27

@Mr_ll

memset 出了问题,初始化层数是不对的


by Zwaire @ 2021-10-30 06:48:42

@Mr_ll

你上面定义的dep 的类型是ll,8个字节啊

但是下面初始化的时候 int 4个字节肯定会初始化出问题


by Mr_ll @ 2021-10-30 14:28:02

@DRY—AYST 谢谢大佬!


|