我开了当前弧优化结果T两个点?

P3376 【模板】网络最大流

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 了,所以你在枚举后面的出边时,是没有流量可以流出的,但是你又把后面的出边标记了。即使在当前轮,u 又接受到了一些流量,也不能给这些后面的出边了。然后就会跑得慢啦。


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 哦,谢谢!!!


|