73tle789点dinic本地运行无法输出

P3376 【模板】网络最大流

AdGats @ 2021-12-22 15:53:56

#include<bits/stdc++.h>
using namespace std;
const int N=205,M=5e3+5;
const long long INF=1e18+5;
long long d[N],delta,ans;
int n,m,s,t,k=1,head[N],cur[N];
queue<int>q;
struct node{
    int v,next;
    long long w;
}edge[M];
inline void addedge(int from,int to,int w){
    edge[++k].next=head[from];
    edge[k].v=to;
    edge[k].w=w;
    head[from]=k;
}
inline int bfs(){
    while(!q.empty())   q.pop();
    memset(d,0,sizeof(d));
    d[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=edge[i].next){
            int v=edge[i].v,w=edge[i].w;
            if(d[v])    continue;
            if(w)   d[v]=d[u]+1,q.push(v); 
        }   
    }
    return d[t];
}
inline long long dfs(int u,long long flow){
    if(u==t)    return flow;
    long long res=0;
    for(int &i=cur[u];i&&flow;i=edge[i].next){
        long long v=edge[i].v,&w=edge[i].w;
        if(d[v]==d[u]+1&&w){
            long long de=dfs(v,min(flow,w));
            if(!de) d[v]=INF;
            w-=de,edge[i^1].w+=de,res+=de,flow-=de;
        }
    }
    if(!res)    d[u]=0;
    return res;
}
inline void dinic(){
    while(bfs()){
        for(int i=1;i<=n;i++)   cur[i]=head[i];
        while(delta=dfs(s,INF)) ans+=delta;
    }
} 
inline int read(){
    int a=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9')   a=a*10+c-'0',c=getchar();
    return a;
}
int main(){
    memset(head,0,sizeof(head));
    n=read(),m=read(),s=read(),t=read();
    for(int i=1;i<=m;i++){
        int x,y,z;
        x=read(),y=read(),z=read(); 
        addedge(x,y,z);
        addedge(y,x,0);
    }
    dinic();
    printf("%lld",ans);
    return 0;
}

by CodingJellyfish @ 2021-12-22 16:05:12

孩子,边数要开双倍


by AdGats @ 2022-11-14 09:20:37

@CodingJellyfish 感谢


|