萌新求助

P3376 【模板】网络最大流

Shiota_Nagisa @ 2023-03-19 15:48:39

#include<bits/stdc++.h>
using namespace std;
struct data{
    int from,to;
    long long wei;
}e[100101];
int head[100011],tot;
void add(int x,int y,int z){
    e[++tot].from=head[x];
    e[tot].to=y;
    e[tot].wei=z;
    head[x]=tot;//正向边 

    e[++tot].from=x;
    e[tot].to=x;
    e[tot].wei=0;
    head[y]=tot;//反向边 
}
int n,m,s,t;
long long d[100011],w,ans=0,sum=0;//d:层次 
int u,v;
int bfs(){
    d[s]=1;
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i!=0;i=e[x].from){
            int y=e[i].to;
            if(!d[y]&&e[i].wei!=0){
                q.push(y);
                d[y]=d[x]+1;
                if(y==t){
                    return 1;
                }
            }
        }
    }
    return 0;
}
int dfs(int p,long long flow){
    if(p==t){
        return flow;
    }
    long long s=0;
    long long res=flow;
    for(int i=head[p];i!=0&&flow!=0;i=e[p].from){
        int y=e[i].to;
        if(e[i].wei&&(d[y]==d[p]+1)){
            s=dfs(y,min(flow,e[i].wei));
            if(s==0) d[i]=1e9;
            res+=s;
            flow-=s;
            e[i].wei-=s;
            e[i^1].wei+=s;  
        }
    }
    return res;
}
int main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
    }
    while(bfs()){
        ans+=dfs(s,1e9);
    }
    cout<<ans<<endl;
    return 0;
}

|