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 因为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♪(・ω・)ノ