为什么?求答

P3376 【模板】网络最大流

MagicLyney_06 @ 2023-11-07 10:04:54

Dinic:

//
// Created by lndff on  2023.11.07
//
#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define int LL

const int N = 210000;
const int M = 501000;
const LL INF = 1123451123123;
template <typename T> inline void read(T &x){
    int w = 1;x = 0;char s;
    while (!isdigit(s = getchar())) if (s == '-') w = -1;
    while (isdigit(s)) x = (x << 3) + (x << 1), x += s - '0', s = getchar();
    x *= w;
}

int n, m, s, t, tot = 1;
int temp[N], head[N], Next[M << 1], ver[M << 1];
LL d[N], w[M << 1];
LL ans;
void add(int u, int v, LL ww){
    ver[++tot] = v;
    w[tot] = ww;
    Next[tot] = head[u];
    head[u] = tot;
}

inline int bfs(){
    for (register int i = 1; i <= n; d[i] = INF, i++);
    queue<int> q;
    q.push(s);
    d[s] = 0;
    temp[s] = head[s];
    while (!q.empty()){
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = Next[i]){
            if (w[i] > 0 && d[ver[i]] == INF){
                q.push(ver[i]);
                temp[ver[i]] = head[ver[i]];
                d[ver[i]] = d[x] + 1;
                if (ver[i] == t) return 1;
            }
        }
    }
    return 0;
}

inline int dfs(int x, LL sumflow){
    if (x == t) return sumflow;
    LL res, ret = 0;
    for (int i = temp[x]; i && sumflow; i = Next[i]){
        temp[x] = i;
        if (w[i] > 0 && (d[ver[i]] == d[x] + 1)){
            res = dfs(ver[i], min(sumflow, w[i]));
            if (!res) d[ver[i]] = INF;
            w[i] -= res;
            w[i ^ 1] += res;
            ret += res;
            sumflow -= res;
        }
    }
    return ret;
}
signed main(){
    read(n), read(m), read(s), read(t);
    LL ww;
    for (register int i = 1, u, v; i <= m; read(u), read(v), read(ww), add(u, v, ww), add(v, u, 0), i++);
    while (bfs()) {ans += dfs(s, INF);}
    return 0 * printf("%lld", ans); 
}

这样就AC了, 删掉#define int LL 就会WA三个点,其中一个甚至爆负,为什么?


by BetterGodPig @ 2023-11-07 10:08:53

@MagicLyney_06 因为1 \le w \le 2^{31},两个 2^{31} 加起来就爆 int 了,更别说边还有那么多


by MagicLyney_06 @ 2023-11-07 10:14:16

@NaHCO3_tht 可是计算部分我是开了LL


by Terrible @ 2023-11-07 10:17:41

int dfs


by MagicLyney_06 @ 2023-11-07 10:40:06

@Terrible Thanks♪(・ω・)ノ


|