没反向边也能过网络最大流???

P3376 【模板】网络最大流

zesqwq @ 2022-04-16 10:50:40

#include <bits/stdc++.h>
using namespace std;

const int M = 5005, N = 201;
struct Edge {
    int next, to, val;
} edge[M * 2];
struct Pre {
    int next, val;
} pre[N];
int h[N], vis[N], n, m, s, t, cnt;
queue<int> q;
void add(int u, int v, int w) {
    edge[++cnt] = { h[u], v, w }, h[u] = cnt;
}
bool bfs(int s, int t) {
    while (!q.empty())
        q.pop();
    memset(vis, 0, sizeof(int) * (n + 1));
    memset(pre, 0, sizeof(Pre) * (n + 1));
    q.push(s);
    vis[s] = 1;
    int u, v, d;
    while (!q.empty()) {
        u = q.front(), q.pop();
        if (u == t)
            return true;
        for (int i = h[u]; i; i = edge[i].next) {
            v = edge[i].to, d = edge[i].val;
            if (d && !vis[v])
                pre[v] = { u, i }, q.push(v), vis[v] = 1;
        }
    }
    return false;
}
void read() {
    cin >> n >> m >> s >> t;
    int l, r, w;
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &l, &r, &w);
        add(l, r, w);// add(r, l, 0);
    }
}
int arg(int s, int t) {
    int minn = 0x3f3f3f3f;
// for (int i = t; i != s; i = pre[i].next)
//  printf("pre[%d]:{%d %d}", i, pre[i].next, edge[pre[i].val].val);
// puts("");
    for (int i = t; i != s; i = pre[i].next)
        minn = min(minn, edge[pre[i].val].val);
    for (int i = t; i != s; i = pre[i].next)
        edge[pre[i].val].val -= minn;// edge[pre[i].val ^ 1].val += minn;
// for (int i = t; i != s; i = pre[i].next)
//  printf("pre[%d]:{%d %d}", i, pre[i].next, edge[pre[i].val].val);
    return minn;
}
long long EK(int s, int t) {
    long long cnt = 0;
    while (bfs(s, t)) {
        cnt += arg(s, t);
//  printf("%lld\n", cnt);
    }
    return cnt;
}
int main() {
    read();
    cout << EK(s, t);
    return 0;
}

看读入 连反向边都没建 pre的val代表那条边的编号


by rxjdasiwzl @ 2022-04-16 11:30:35

@zhouershan 老问题,数据太水


by rxjdasiwzl @ 2022-04-16 11:30:55

看一下这题之前的讨论区


by 柳下惠 @ 2022-04-16 11:47:14

@zhouershan 这个题不建就跑不过去了


by juruoCms @ 2022-08-13 16:26:15

@zhouershan 啊对对对


|