社区讨论

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

P3376【模板】网络最大流参与者 3已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@lo8phw9i
此快照首次捕获于
2023/10/27 22:26
2 年前
此快照最后确认于
2023/10/27 22:26
2 年前
查看原帖
这是不开当前弧优化的版本,但是没有T,可以过(虽然比较慢)
CPP
#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两个点?

回复

7 条回复,欢迎继续交流。

正在加载回复...