YCSluogu @ 2022-06-28 08:06:20
这是不开当前弧优化的版本,但是没有T,可以过(虽然比较慢)
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int kMaxN = 1e6;
struct edge {
long long v, w, next;
}e[kMaxN];
int head[kMaxN];
int tot = 1;
int s, t;
int level[kMaxN];
int cur[kMaxN];
int n, m;
void add(int u, int v, int w) {
e[++tot] = {v, w, head[u]};
head[u] = tot;
}
bool bfs() {
memset(level, 0, sizeof(level));
queue<int> q;
q.push(s);
level[s] = 1;
while (!q.empty()) {
int f = q.front();
q.pop();
for (int i = head[f]; i; i = e[i].next) {
int v = e[i].v;
if (!level[v] && e[i].w) {
level[v] = level[f] + 1;
q.push(v);
}
}
}
return level[t];
}
long long dfs(int u, long long in) {
if (u == t) return in;
long long out = 0;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (e[i].w && level[v] == level[u] + 1) {
long long res = dfs(v, min(e[i].w, in));
out += res;
in -= res;
e[i].w -= res;
e[i ^ 1].w += res;
}
}
if (out == 0) level[u] = 0;
return out;
}
int main() {
cin >> n >> m >> s >> t;
for (int i = 1, u, v, w; i <= m; i++) {
cin >> u >> v >> w;
add(u, v, w);
add(v, u, 0);
}
long long ans = 0;
while (bfs()) {
ans += dfs(s, 1e9);
}
cout << ans << endl;
return 0;
}
但是我开了当前弧优化就? TLE两个点?
跑的更慢了?
by coder_1746 @ 2022-06-28 08:25:51
P某某76也许厌氧
by Froranzen @ 2022-06-28 08:38:15
在这里
if (e[i].w && level[v] == level[u] + 1) {
long long res = dfs(v, min(e[i].w, in));
out += res;
in -= res;
e[i].w -= res;
e[i ^ 1].w += res;
}
如果 in = 0
,你要及时返回。
by Froranzen @ 2022-06-28 08:40:57
因为 in = 0
了,所以你在枚举后面的出边时,是没有流量可以流出的,但是你又把后面的出边标记了。即使在当前轮,
by Froranzen @ 2022-06-28 08:43:12
大概是这个意思(
by Froranzen @ 2022-06-28 08:43:36
好像 dinic 不开当前弧优化,复杂度是错的
by Froranzen @ 2022-06-28 08:49:28
评测记录
只加了上面提到的 in = 0
就返回的优化,不开 O2 已经能跑到 300ms 了
by YCSluogu @ 2022-06-29 14:40:36
@Froranzen 哦,谢谢!!!