73分dinic求助大佬

P3376 【模板】网络最大流

Dark_lightrq @ 2023-03-30 15:45:01

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=205,M=10005;
const LL INF=(1ll<<60)-1;
struct netflow{
    int n,m,s,t;
    int head[N],nxt[M],tot,ver[M];
    LL w[M];

    void add_(int x,int y,LL z){
        ver[++tot]=y,nxt[tot]=head[x],head[x]=tot,w[tot]=z;
        ver[++tot]=x,nxt[tot]=head[y],head[y]=tot,w[tot]=0;
    }
    int q[N],lev[N],cur[N];
    bool bfs(){
        for(int i=1;i<=n;i++){
            lev[i]=0,cur[i]=head[i];
        }
        lev[s]=1;
        int l,r;
        q[l=r=1]=s;
        while(l<=r){
            int x=q[l++];
            for(int i=head[x];i;i=nxt[i]){
                int y=ver[i];
                if(w[i]&&!lev[y]){
                    lev[y]=lev[x]+1;
                    q[++r]=y;
                    if(y==t)return 1;
                }
            }
        }
        return 0;
    }
    int dfs(int x,LL flow){
        if(x==t)return flow;
        LL res=0;
        for(int &i=cur[x];i;i=nxt[i]){
            int y=ver[i];
            if(w[i]&&lev[y]==lev[x]+1){
                int k=dfs(y,min(flow,w[i]));
                flow-=k;
                res+=k;
                w[i]-=k;
                w[i^1]+=k;
                if(!flow)break;
            }
        }
        if(!res)lev[x]=0;
        return res;
    }
    LL dinic(){
        LL ans=0;
        while(bfs()){
            ans+=dfs(s,INF);
        }
        return ans;
    }
}T;
int main(){
    T.tot=1;
    scanf("%d%d%d%d",&T.n,&T.m,&T.s,&T.t);
    for(int i=1;i<=T.m;i++){
        int x,y;
        LL z;
        scanf("%d%d%lld",&x,&y,&z);
        T.add_(x,y,z);
    }
    cout<<T.dinic();
    return 0;
}

by Dark_lightrq @ 2023-03-30 15:53:19

WA了7,8,10


by AlicX @ 2023-03-30 16:02:42

在 Dinic 中你需要判断一下 k 是否为 0,如果为 0,就要写一个 lev_i=0


by AlicX @ 2023-03-30 16:03:15

lev_y=0

by Dark_lightrq @ 2023-03-30 16:07:34

@zhengdongwen 可是还是错了啊


by Dark_lightrq @ 2023-03-30 23:31:40

int dfs改为LL dfs就过了


by longlinyu7 @ 2024-06-23 19:46:55

@Dark_lightrq 好人一生平安,犯的错跟你一模一样


|