MnZn求助网络流，本地AC，上交10个点RE

cjZYZtcl @ 2023-04-06 09:53:14

by cjZYZtcl @ 2023-04-06 09:53:28

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pr pair<int, int>
#define mp make_pair
#define pb push_back
#define mid (l + r) / 2
#define fi first
#define se second
const int N = 20005, inf = 0x7ffffffffffll;

struct node {
    int to, val, id;

    node (int to = 0, int val = 0, int id = 0) : to(to), val(val), id(id) {}
};
vector<node> v[N];
int vis[N], s, t;

inline int read(){
    int x = 0, mm = 1;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') mm = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * mm;
}

inline void write(int x){
    if(x < 0){
        putchar('-');
        write(-x);
        return;
    }
    if(x >= 10) write(x / 10);
    putchar(x % 10 + '0');
}

int dfs(int ro, int flow) {
    if (ro == t) return flow;

    vis[ro] = 1;

    for (int i = 0; i < (int)v[ro].size(); i++) {
        node &to = v[ro][i];

        if (!vis[to.to] && to.val > 0) {
            int d = dfs(to.to, min(flow, to.val));

            if (d) {
                to.val -= d;
                v[to.to][to.id].val += d;

                return d;
            }
        }
    }
}

int Ford_Fulkerson() {
    int flow = 0;

    while (1) {
        memset(vis, 0, sizeof(vis));

        int f = dfs(s, inf);

        if (!f) return flow;

        flow += f;
    }
}

signed main(){
    int n = read(), m = read();
    s = read(), t = read();

    for (int i = 1; i <= m; i++) {
        int x = read(), y = read(), z = read();

        v[x].pb(node(y, z, v[y].size()));
        v[y].pb(node(x, 0, v[x].size() - 1));
    }

    write(Ford_Fulkerson());
}

by cjZYZtcl @ 2023-04-06 09:57:05

问题找到了，DFS未返回，此贴完结

by Fido_Puppy @ 2023-04-06 12:22:37

@cjZYZtcl 大佬好强！

by cjZYZtcl @ 2023-04-06 12:26:04

@Fido_Puppy wyy,jbl