我开了当前弧优化结果T两个点?
查看原帖
我开了当前弧优化结果T两个点?
311721
YCSluogu楼主2022/6/28 08:06

这是不开当前弧优化的版本,但是没有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两个点?

跑的更慢了?

2022/6/28 08:06
加载中...