关于本题的迷惑行为

P3376 【模板】网络最大流

Stinger @ 2021-04-09 15:05:56

就是我如果在EK中建了反向边就WA37,不加反向边不仅AC还跑得飞快,请问这是什么原因呢?

加反向边:

#include <cstdio>
#include <queue>
#include <cstring>
#define int long long

const int INF = 1e15;
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
    int from, to, nxt, cap, flow;
} e[10005];
int head[205], a[205], p[205], tot, s, t;
inline void AddEdge(const int u, const int v, const int w) {
    e[++ tot].from = u, e[tot].to = v, e[tot].nxt = head[u], head[u] = tot;
    e[tot].flow = 0, e[tot].cap = w;
}
std::queue<int> Q;

int Edmonds_Karp()  {
    int flow(0);
    do {
        while (Q.size()) Q.pop();
        Q.push(s);
        memset(a, 0, sizeof a);
        a[s] = INF;
        while (Q.size() && !a[t]) {
            int u(Q.front());
            Q.pop();
            for (int i(head[u]); i; i = e[i].nxt) {
                const int v(e[i].to);
                if (!a[v] && e[i].cap > e[i].flow)
                    a[v] = min(a[u], e[i].cap - e[i].flow), p[v] = i, Q.push(v);
            }
        }
        for (int i(t); i != s; i = e[p[i]].from)
            e[p[i]].flow += a[t], e[p[i] ^ 1].flow -= a[t];
        flow += a[t];
    } while (a[t]);
    return flow;
}

signed main() {
    int n, m;
    scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
    for (int i(1); i <= m; ++ i) {
        int u, v, w;
        scanf("%lld%lld%lld", &u, &v, &w);
        AddEdge(u, v, w);
        AddEdge(v, u, 0);
    }
    printf("%lld", Edmonds_Karp());
    return 0;
}

不加:

#include <cstdio>
#include <queue>
#include <cstring>
#define int long long

const int INF = 1e15;
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
    int from, to, nxt, cap;
} e[10005];
int head[205], a[205], p[205], tot, s, t;
inline void AddEdge(const int u, const int v, const int w) {
    e[++ tot].from = u, e[tot].to = v, e[tot].nxt = head[u], head[u] = tot, e[tot].cap = w;
}
std::queue<int> Q;

int Edmonds_Karp()  {
    int flow(0);
    while (true) {
        while (Q.size()) Q.pop();
        Q.push(s);
        memset(a, 0, sizeof a);
        memset(p, 0, sizeof p);
        a[s] = INF;
        while (Q.size() && !a[t]) {
            int u(Q.front());
            Q.pop();
            for (int i(head[u]); i; i = e[i].nxt) {
                const int v(e[i].to);
                if (!a[v] && e[i].cap)
                    a[v] = min(a[u], e[i].cap), p[v] = i, Q.push(v);
            }
        }
        if (!a[t]) break;
        for (int i(t); i != s; i = e[p[i]].from)
            e[p[i]].cap -= a[t];
        flow += a[t];
    }
    return flow;
}

signed main() {
    int n, m;
    scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
    for (int i(1); i <= m; ++ i) {
        int u, v, w;
        scanf("%lld%lld%lld", &u, &v, &w);
        AddEdge(u, v, w);
    }
    printf("%lld", Edmonds_Karp());
    return 0;
}

by xzggzh1 @ 2021-04-09 15:10:55

@zhangqs 你的边数有没有初始化为 1


by Stinger @ 2021-04-09 15:11:23

@xzggzh1 我的边数一开始图是空的,tot0


by xzggzh1 @ 2021-04-09 15:12:37

@zhangqs tot=1 就过了


by Stinger @ 2021-04-09 15:12:54

@xzggzh1 好的,我懂了,我是伞兵,谢谢您。


|