题解 SS231107C【爬梯高手】

撞原了，好耶！Gym 102341B 顺便把我的变异加强版爆标了！！！

problem

有一个 \(n*m\) 个点的有向分层图，共有 \(n\) 层，每层 \(m\) 个点，每条边一定是从第 \(i\) 层连向第 \(i+1\) 层。

定义 \(f(i,j)\) 表示选择若干条路径，每条路径从第 \(i\) 层出发，在第 \(j\) 层结束，且每条路径在顶点和边上都不交的情况下，最多选择的路径数。

求 \(\sum\limits_{i=1}^n\sum\limits_{j=i+1}^nf(i,j)\)。

\(n\leq 40000, k\leq 9\)。

solution \(O(nk^22^k)\)

题目说的就是 \(i\to j\) 列的最大流，直接改成最小割（注意这里最小割是割点）。我们思维跳跃一下，设：\(f_{i, S, j}\) 表示一个最大的左端点 \(l\)，使得从 \(l\) 出发时，现在最小割是 \(j\)（割了 \(j\) 个点），现在已经被割得在第 \(i\) 列的 \(S\) 的位置们结束（\(S\in 2^k\)）。这里对流的定义比较奇怪，看作是一些神秘的连通性？然后考虑转移了。

\[f_{i, neighbour(S), j}=\max_{S}f_{i-1, S, j} \]

从上一层流过来。

\[f_{i, \varnothing, 0}=i \]

\[f_{i, S, j} = \max_{u\in S}f_{i, S\backslash\{u\}, j-1} \]

在这一层割点。高维前缀和。

最后答案记 \(sum_j=\sum_{i, S}f_{i, S, j}\)，然后做差分，就是每种流量的出现次数，记得减掉自己的。

solution \(O(nk^3)\)

考虑固定左端点之后暴力向后流，例如 \(F(1, n)\)，流满了以后把最后的一些点删掉，删到增广最远的地方，然后继续流。移动左端点只需要把左端点删掉，其实不用删掉，就是源点连向新的一列，用一些残量网络加边判连通性的技巧保证复杂度为 \(O(nk^3)\)。

code

solution 1

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
int n, m;
char g[40010][10][10];
int f[2][512][10], gb[9];
LL sum[10];
LL dp() {
  for (int i = 1; i <= n; i++) {
    memset(gb, 0, sizeof gb);
    for (int u = 0; u < m; u++) {
      for (int v = 0; v < m; v++) {
        if (g[i - 1][u][v] == '1') gb[v] |= 1 << u;
      }
    }
    memset(f[i & 1][0], 0, sizeof f[i & 1][0]);
    f[i & 1][0][0] = i;
    for (int S = 1; S < 1 << m; S++) {
      int preS = 0;
      for (int v = 0; v < m; v++) if (S >> v & 1) preS |= gb[v];
      memcpy(f[i & 1][S], f[i & 1 ^ 1][preS], sizeof f[i][S]);
      for (int j = 1; j <= m; j++) {
        for (int u = 0; u < m; u++) 
          if (S >> u & 1) f[i & 1][S][j] = max(f[i & 1][S][j], f[i & 1][S ^ (1 << u)][j - 1]);
      }
    }
    int U = (1 << m) - 1;
    for (int j = 0; j <= m; j++) if (f[i & 1][U][j]) sum[j] += f[i & 1][U][j];
//  for (int S = 0; S < 1 << m; S++)
//    for (int j = 0; j <= m; j++)
//      debug("f[%d][%d][%d] = %d\n", i, S, j, f[i][S][j]);
  }
  LL ans = 0;
  for (int j = 0; j <= m; j++) debug("sum[%d] = %d\n", j, sum[j]);
  for (int j = m; j >= 1; j--) sum[j] -= sum[j - 1];
  sum[m] -= n;
  for (int j = 0; j <= m; j++) ans += sum[j] * j;
  return ans;
}
int main() {
#ifndef NF
  freopen("stairs.in", "r", stdin);
  freopen("stairs.out", "w", stdout);
  cin.tie(nullptr)->sync_with_stdio(0);
#endif
  cin >> n >> m;
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < m; j++) cin >> g[i][j];
  }
  cout << dp() << endl;
  return 0;
}