32ptsFord-Fulkerson求助

P3376 【模板】网络最大流

FateReset_ @ 2023-07-24 15:34:27

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
vector< vector<int> > e;
int fordFulkerson(int s, int t){    
    int u,v;
    int max_flow=0;
    vector<vector<int>> rGraph=e; 
    while(true){
        vector<int> parent(n,-1);  
        queue<int> q;
        q.push(s);
        parent[s]=-2;
        while (!q.empty() && parent[t]==-1){
            int cur=q.front();
            q.pop();
            for(int i=1;i<=n;i++){
                if(rGraph[cur][i]>0 && parent[i]==-1){
                    parent[i]=cur;
                    q.push(i);
                }
            }
        }
        if(parent[t]==-1) break; 
        int path_flow=INT_MAX; 
        for(v=t;v!=s;v=parent[v]){
            u=parent[v]; 
            path_flow=min(path_flow, rGraph[u][v]); 
        }
        for(v=t;v!=s;v=parent[v]){
            u=parent[v]; 
            rGraph[u][v]-=path_flow; 
            rGraph[v][u]+=path_flow;
        }   
        max_flow+=path_flow;
    }   
    return max_flow;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    e.resize(n + 1, vector<int>(n + 1, 0));
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        e[u][v]=w;
    }
    cout<<fordFulkerson(s,t);
    return 0;
}

by FateReset_ @ 2023-07-24 15:35:38

评测记录


|