萌新求助，悬赏关注

Shiota_Nagisa @ 2023-03-24 20:54:35

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

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

by LgxTpre @ 2023-03-24 21:06:57

@Manchester_Utd_FC 已知的问题包括但不限于：

• dfs中res的初值是否应该为0
• bfs遍历边的终止条件是否应该为i
• 神秘的边标号方式
• 没有写当前弧优化

by yizhiming @ 2023-03-24 21:21:13

@Manchester_Utd_FC 自己看吧，有错的地方都标出来了

#include<bits/stdc++.h>
using namespace std;
struct data{
    int from,to;
    long long wei;
}e[100101];
int head[100011],tot=1;
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=head[y];
    e[tot].to=x;
    e[tot].wei=0;
    head[y]=tot;//反向边 
}
int n,m,s,t;
long long d[100011],w,ans=0;//d:层次 
int u,v;
int bfs(){
    memset(d, 0, sizeof(d)); 
    d[s]=1;
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=e[i].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;
}
long long dfs(int p,long long flow){//这里 
    if(p==t){
        return flow;
    }
    long long s=0;
    long long res=0;//这里 
    for(int i=head[p];i&&flow;i=e[i].from){
        int y=e[i].to;
        if(e[i].wei&&(d[y]==d[p]+1)){
            s=dfs(y,min(flow,e[i].wei));
            res+=s;
            flow-=s;
            e[i].wei-=s;
            e[i^1].wei+=s;  
        }
    }
    if(!res) d[p]=-1;
    return res;
}
int main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
    }
//  cout<<endl;
    while(bfs()){
        ans+=dfs(s,1e9);
    }
    cout<<ans<<endl;
    return 0;
}