dinic板子的一个问题
  • 板块灌水区
  • 楼主YCSluogu
  • 当前回复18
  • 已保存回复18
  • 发布时间2023/8/14 13:59
  • 上次更新2023/11/3 03:54:29
查看原帖
dinic板子的一个问题
311721
YCSluogu楼主2023/8/14 13:59
  for (int& i = cur[u]; i; i = e[i].next) {
    int v = e[i].v;
    if (e[i].cap && level[v] == level[u] + 1) {
      long long res = dfs(v, std::min(in, e[i].cap));
      e[i].cap -= res, e[i ^ 1].cap += res;
      in -= res, out += res;
      if (in == 0) break;
    }
  }

复杂度是对的,但是

  for (int& i = cur[u]; i && in; i = e[i].next) {
    int v = e[i].v;
    if (e[i].cap && level[v] == level[u] + 1) {
      long long res = dfs(v, std::min(in, e[i].cap));
      e[i].cap -= res, e[i ^ 1].cap += res;
      in -= res, out += res;
    }
  }

却会TLE

(这是为什么

2023/8/14 13:59
加载中...