32pts求助,大红大紫

P3376 【模板】网络最大流

New_hope @ 2023-08-26 21:16:54

#include<bits/stdc++.h>
#define N 205
#define int long long
using namespace std;

struct E {
    int ed,c;
};
vector<E> a[N],b[N]; // a 正边,b 反边 
queue<int> q;

int n,m,s,t,ans;
int d[N];

bool bfs() {
    memset(d,0,sizeof(d));
    while(!q.empty()) q.pop();
    q.push(s); d[s] = 1;
    while(!q.empty()) {
        int fr = q.front(); q.pop();
        for(auto j : a[fr]) {
            int v = j.ed, c = j.c;
            if(!d[v] && c) {
                d[v] = d[fr] + 1;
                if(v == t) return true;
                q.push(v);
            }
        }
    }
    return false;
}

int dfs(int u,int minf) {
    if(u == t) return minf;
    int sum = 0;
    for(int i = 0; i < a[u].size(); i ++) {
        int v = a[u][i].ed, w = a[u][i].c;
        if(d[v] == d[u]+1 && w) {
            int f = dfs(v,min(minf,w));
            a[u][i].c -= f;
            b[v][i].c += f;
            minf -= f;
            sum += f;
            if(minf <= 0) break;
        }
    }
    if(sum == 0) d[u] = 0;
    return sum;
}
signed main() {

    cin >> n >> m >> s >> t;
    for(int i = 1; i <= m; i ++) {
        int u,v,w;
        cin >> u >> v >> w;
        a[u].push_back({v,w});  
        b[v].push_back({u,0});  
    }

    int Max = 1 << 31;
    while(bfs()) {
        ans += dfs(s,Max);
    }
    cout << ans;

    return 0;
} 

by g1ove @ 2023-08-26 21:19:20

bfsdfs 时正反边都要考虑 建议remake 链式前向星


by g1ove @ 2023-08-26 21:20:43

@New_hope 改的话 ab 算边时都遍历一次


by New_hope @ 2023-08-26 21:22:50

@g1ove 感谢


|