「SOL」网络流flow (模拟赛)

题面

给定一张分层有向图，有 \(n\) 层，每层有 \(m\) 个点。只有从第 \(i\) 层的点连向第 \(i + 1\) 层的点的连边。

记 \(A(i,j)\) 表示从第 \(i\) 层的某些点出发到第 \(j\) 层的某些点的点不相交路径集合的最大大小。求

\[\sum_{i=1}^n\sum_{j=i+1}^n A(i,j)
\]

其中，\(n\le 4\times10^4,m\le10\)。

解析

注意到 \(m\) 很小，于是首先有一个暴力状压的思路。\(f(i,S)\) 表示从第 \(i\) 层的 \(S\) 点集出发，要求这 \(|S|\) 条路径都能到达第 \(j\) 层，\(j\) 最大是多少。

可以 DFS 出所有第 \(i\) 层和第 \(i + 1\) 层之间的转移，总复杂度 \(\mathcal{O}(2^{2m}n)\)。统计答案则可以记 \(g(i,k)\)：

\[g(i,k)=\max_{|S|=k}f(i,S)
\]

则 \(A(i, j) = k\)（\(g(i, k) \le j \le g(i, k + 1)\)），可以快速统计答案。

考虑这样 DP 的本质是什么。假如把原问题建网络流，只需要把每个点拆点限制流量，就相当于求两层之间的最大流。

而状压 DP 反映的是这样一个结论：从第 \(i\) 层出发，可以在任意位置结束，尽可能流到较大的层；在这样的前提下流最大流，则 \(A(i,j)\) 为流经第 \(j\) 层的流量。

相当于一个费用流，两层之间费用为 \(1\)。（实际上也没有这样去实现代码，只是方便理解）

考虑到这个流网络非常特殊，可以模拟流的过程。

由于可以在任何位置结束，所以一定是满流的，只需要每次找到残留网络的最长路——即能够到达的最深的层。
可以直接 BFS，由于费用只和点的层数有关，所以一个点不需要多次更新，过程中维护点的访问标记。
记录增广路的前驱，在找到层数最大的增广路后逆序还原增广路，更新残留网络。
由于流网络分层，不可能从较大的层流向较小的层，于是将源点从第 \(i\) 层换到第 \(i + 1\) 层时，可以直接继承残留网络，删去 \(i\) 和 \(i + 1\) 层之间的连边。

最后就是时间复杂度的问题了。注意到假如在一次增广时，找到的增广路层数为 \(p\)，则最多访问 \(pk\) 个点，每个点转移复杂度 \(\mathcal{O}(k)\)，则该次增广复杂度为 \(\mathcal{O}(pk^2)\)。

该次增广后，流网络的总流量增加 \(\mathcal{O}(p)\)（手动模拟一下，可以发现即使发生退流，由于我们取层数最大的增广路，退掉的流也会补回来，该次增广仍会使流网络总流量增加 \(p\)），而流网络总流量 \(\mathcal{O(nk)}\)，所以 \(\mathcal{O}(\sum pk^2)=\mathcal{nk^3}\)。

模拟细节见代码。

源代码

/* Lucky_Glass */

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

typedef long long llong;

typedef std::pair<int, int> pii;

int rin(int &r) {

  int c = getchar(); r = 0;

  while (c < '0' || '9' < c) c = getchar();

  while ('0' <= c && c <= '9') r = r * 10 + (c ^ '0'), c = getchar();

  return r;

}

const int N = 4e4 + 10, K = 10;

int n, m, nw, tot_flw;

int lnk[N << 1][K], lnk_i[N << 1][K], vis[N << 1];

int elg2[(1 << K) + 10], flw_cnt[N];

pii las_pnt[N << 1][K];

void extend(const int &sx, const int &sy) {

  int ed_x = sx, ed_y = sy;

  int clear_vis_pos = sx;

  vis[sx] = 1 << sy;

  /* 此次增广经过的第 i 层点（防止环流？） */

  std::queue<pii> que;

  que.emplace(sx, sy);

  while (!que.empty()) {

    int ux = que.front().first, uy = que.front().second;

    que.pop();

    if ((ux & 1) && (ux >> 1) > (ed_x >> 1))

      ed_x = ux, ed_y = uy;

    /* 向下一层 */

    if (ux < nw) {

      if (clear_vis_pos == ux) vis[++clear_vis_pos] = 0;

      int rem = lnk[ux][uy] ^ (lnk[ux][uy] & vis[ux + 1]);

      while (rem) {

        int vy = elg2[rem & -rem];

        vis[ux + 1] |= 1 << vy;

        /* las_pnt 记录转移点，便于还原增广路 */

        las_pnt[ux + 1][vy] = std::make_pair(ux, uy);

        que.emplace(ux + 1, vy);

        rem ^= rem & -rem;

      }

    }

    /* 经过逆向边返回上一层，lnk_i 存储反向边 */

    if (ux > sx) {

      int rem = lnk_i[ux][uy] ^ (lnk_i[ux][uy] & vis[ux - 1]);

      while (rem) {

        int vy = elg2[rem & -rem];

        vis[ux - 1] |= 1 << vy;

        las_pnt[ux - 1][vy] = std::make_pair(ux, uy);

        que.emplace(ux - 1, vy);

        rem ^= rem & -rem;

      }

    }

  }

  /* 更新每一层的流量，更新答案 */

  for (int i = sx >> 1, lmt_i = ed_x >> 1; i <= lmt_i; ++i)

    ++flw_cnt[i], ++tot_flw;

  /* 还原增广路，更新残留网络 */

  while (ed_x != sx || ed_y != sy) {

    // printf("(%d, %d) <- ", ed_x, ed_y);

    int lasx = las_pnt[ed_x][ed_y].first,

        lasy = las_pnt[ed_x][ed_y].second;

    if (ed_x == lasx + 1) {

      lnk[lasx][lasy] ^= 1 << ed_y;

      lnk_i[ed_x][ed_y] ^= 1 << lasy;

    } else {

      lnk[ed_x][ed_y] ^= 1 << lasy;

      lnk_i[lasx][lasy] ^= 1 << ed_y;

    }

    ed_x = lasx, ed_y = lasy;

  }

  // printf("(%d, %d)\n", sx, sy);

}

void init() {

  for (int i = 0; i <= K; ++i)

    elg2[1 << i] = i;

}

int main() {

  freopen("flow.in", "r", stdin);

  freopen("flow.out", "w", stdout);

  // freopen(".\\input\\input.in", "r", stdin);

  init();

  rin(n), rin(m);

  nw = (n << 1) - 1;

  for (int i = 1; i < nw; ++i)

    if (i & 1) {

      static char inp[K << 1];

      for (int j = 0; j < m; ++j) {

        scanf("%s", inp);

        for (int k = 0; k < m; ++k)

          lnk[i][j] |= (inp[k] ^ '0') << k;

      }

    } else {

      for (int j = 0; j < m; ++j)

        lnk[i][j] = 1 << j;

    }

  llong ans = 0;

  for (int i = 1; i < n; ++i) {

    for (int j = 0; j < m; ++j)

      extend(std::max(1, (i - 1) << 1), j);

    /*

     * 注意一定是从 (i - 1) << 1 开始

     * 通过 ((i - 1) << 1) -> (((i - 1) << 1) - 1) 是否有边

     * 限制每个点只能用一次

     * 因为第一层不存在访问多次，可以直接从 1 开始跑

     */

    ans += (tot_flw -= flw_cnt[i - 1]);

  }

  printf("%lld\n", ans);

  return 0;

}

THE END

Thanks for reading!

扬起远航的帆
谁在轻声呼唤
萦绕在耳畔
到达心的彼岸
一切宛如梦幻
又归于平淡

——《巫山云》By Snapmod / 诗岸

> Link 巫山云 - 网易云

巴特西

「SOL」网络流flow (模拟赛)

题面

解析

源代码

THE END

Thanks for reading!

最新文章

热门文章