题解：P9902 『PG2』模拟最大流

· · 题解

比较好的 DP 题。第一反应是暴力跑最大流，但是卡常难度极高，所以就算了 QAQ。

注意到这是一个 DAG，有拓扑序 1,2,3\ldots,n，并且一个点只有前面最多七个点向它有边。注意到图的形式非常优美，考虑 DP。

直接从最大流 DP 似乎不太可行，使用经典 Trick 最大流转最小割，直接设 dp_{i,S} 表示 i 点，[i-k,i] 区间中的点是否和源点连通（指从源点可达）的最小割权值。不妨设连通为 1，不连通为 0。那么显然有转移：

dp_{i,S}\to dp_{i+1,(2S+1)\&(2^k-1)}

因为你让 i+1 这个点可达，就不需要割掉额外的边，显然不割边是最优的。有可能实际上你不割边 i+1 也不可达，但是这种情况一定不是最优的，因为前面割了多余的边，可以忽略。

接着是 i+1 不可达的情况。也就是，我们需要把 S 中到 i+1 的边全部割掉。直接暴力枚举是 O(nk2^k)，好像过不去。所以尝试预处理这个东西。

不妨设 f_{i,S} 表示 i 点转移到 i+1 需要切掉集合 S 的边的最小代价。记 e_{i,p} 表示所有 i-p\to i 的边权和，\operatorname{ctz}(x) 表示 x 二进制下最低位的位置。那么有如下转移：

f_{i,S}=f_{i,S\oplus2^{\operatorname{ctz}(S)}}+e_{i+1,\operatorname{ctz}(S)+1}

很好理解，就是加上最后一条边的贡献。初始有 f_{i,0}=0，因为你边都没有，所以不需要割。最后 dp 的转移就变为了：

dp_{i,S}+f_{i,S}\to dp_{i+1,2S\&(2^k-1)}

其中箭头表示 chkmin。统计答案的时候，只需要要求 n 从 1 不可达就行了，也就是 \min_{0\leq S\leq 2^{k-1}-1}dp_{n,2S}。所以现在就可以做了，时空复杂度 O(n2^k)。

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i ++ )
#define per(i, l, r) for(int i = (l); i >= (r); i -- )
#define ctz(x) __builtin_ctz(x)
#define endl '\n'
using namespace std;

const int N = 8e4 + 5;
const int K = 8, INF = 0x3f3f3f3f;
int n, m, k, e[N][K], dp[N][1 << K], f[N][1 << K];
inline int& chkmin(int &x, int v) { return x = x < v ? x : v;}

int main() {
  ios :: sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m >> k;
  rep(i, 1, m) {
    int u, v, w;
    cin >> u >> v >> w;
    if(u == v) continue;
    e[v][v - u] += w;
  }
  memset(dp, 0x3f, sizeof dp);
  rep(S, 0, (1 << (k - 1)) - 1) dp[1][S << 1 | 1] = 0;
  rep(i, 1, n) {
    rep(S, 1, (1 << k) - 1)
      f[i][S] = f[i][S ^ (1 << ctz(S))] + e[i + 1][ctz(S) + 1];
  }
  rep(i, 1, n) {
    rep(S, 0, (1 << k) - 1) {
      chkmin(dp[i + 1][(S << 1 | 1) & ((1 << k) - 1)], dp[i][S]);
      chkmin(dp[i + 1][(S << 1) & ((1 << k) - 1)], dp[i][S] + f[i][S]);
    }
  }
  int ans = INF;
  rep(S, 0, (1 << (k - 1)) - 1) chkmin(ans, dp[n][S << 1]);
  cout << ans << endl;
  return 0;
}