0pts求助,悬赏一关

P3376 【模板】网络最大流

Tjaweiof @ 2023-12-27 21:22:50

RT,提交记录

#include <bits/stdc++.h>
using namespace std;
int fl[201], wlevel[201][201];
pair <int, int> wraw[201][201];
vector <int> raw[201], level[201];
void make(int s){
    memset(fl, 0, sizeof fl);
    for (int i = 1; i <= 200; i++){
        level[i].clear();
    }
    queue <int> q;
    q.push(s);
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (auto v : raw[u]){
            if (wraw[u][v].second && !fl[v]){
                q.push(v);
                fl[v] = fl[u] + 1;
                level[u].push_back(v);
                wlevel[u][v] = wraw[u][v].second;
            }
        }
    }
    return;
}
int dfs(int x, int t, int ans){
    if (x == t){
        return ans;
    }
    if (fl[x] >= fl[t]){
        return 0;
    }
    int res = 0;
    for (auto u : level[x]){
        if (wlevel[x][u]){
            int d = dfs(u, t, min(ans, wlevel[x][u]));
            res += d;
            wraw[x][u].second -= d;
        }
    }
    return res;
}
int dinic(int s, int t){
    int ans = 0;
    while (true){
        make(s);
        if (!fl[t]){
            break;
        }
        ans += dfs(s, t, 2147483647);
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, s, t, u, v, w;
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++){
        cin >> u >> v >> w;
        raw[u].push_back(v);
        wraw[u][v] = {w, w};
    }
    cout << dinic(s, t);
    return 0;
}

by keep_of_silence @ 2023-12-28 08:13:15

@Tjaweiof 网络流要建双向边


by Tjaweiof @ 2023-12-28 12:09:35

@keep_of_silence 感谢


|