WA76pts求助,悬赏一关

P3376 【模板】网络最大流

Tjaweiof @ 2023-12-29 21:22:44

RT,提交记录

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

by Paradise_Lost @ 2023-12-29 21:50:12

@Tjaweiof

没考虑重边,而且你为什么加了两次边?


by Tjaweiof @ 2023-12-30 18:31:09

@Paradise_Lost ?什么加两次边?


by Paradise_Lost @ 2023-12-30 19:00:55

@Tjaweiof

可能是我没看懂你写法,试一下把

wraw[u][v] = w;

改成

wraw[u][v] += w;

by Tjaweiof @ 2023-12-31 06:42:33

@Paradise_Lost 过了,感谢


by Tjaweiof @ 2023-12-31 06:42:53

@Paradise_Lost 已关


|