Luogu P2515 [HAOI2010]软件安装

题目链接：​​传送门​​

很明显，如果图中有一个环
那么这个环上的点必须都要选
那我们一开始就直接缩点
因为每个物品有价值有重量还有有重量限制
所以是很明显的树上背包
我们不确定一开始选哪一个点
所以建一个虚点
入度为0的点像这个虚点连边
然后做树上背包
细节蛮多
数组卡着开

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
struct node {int next, to;}e[A << 1];
int head[A], num;
void add(int fr, int to) {
  e[++num].next = head[fr];
  e[num].to = to;
  head[fr] = num;
}
int dfn[A], low[A], n, m, bl[A], sta[A], top, kn, cnt; bool vis[A];
int w[A], v[A], sum[A], val[A], d[A], in[A], f[A][A * 5];
void tarjan(int fr) {
  dfn[fr] = low[fr] = ++cnt; sta[++top] = fr; vis[fr] = 1;
  for (int i = head[fr]; i; i = e[i].next) {
    int ca = e[i].to;
    if (!dfn[ca]) tarjan(ca), low[fr] = min(low[fr], low[ca]);
    else if (vis[ca]) low[fr] = min(low[fr], dfn[ca]);
  }
  if (dfn[fr] == low[fr]) {
    kn++; int p;
    do {
      p = sta[top--]; vis[p] = 0;
      sum[kn] += w[p]; val[kn] += v[p];
      bl[p] = kn;
    } while (p != fr);
  }
}
void dfs(int fr) {
  for (int i = sum[fr]; i <= m; i++) f[fr][i] = val[fr];
  for (int i = head[fr]; i; i = e[i].next) {
    int ca = e[i].to; dfs(ca);
    for (int j = m - sum[fr]; j >= 0; j--)
      for (int k = 0; k <= j; k++)
        f[fr][j + sum[fr]] = max(f[fr][j + sum[fr]], f[fr][j + sum[fr] - k] + f[ca][k]);
  }
}

int main(int argc, char const *argv[]) {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> w[i];
  for (int i = 1; i <= n; i++) cin >> v[i];
  for (int i = 1; i <= n; i++) {
    cin >> d[i];
    if (!d[i]) continue;
    add(d[i], i);
  }
  for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
  memset(head, 0, sizeof head); num = 0;
  for (int i = 1; i <= n; i++) if (bl[d[i]] != bl[i] and d[i]) add(bl[d[i]], bl[i]), in[bl[i]]++;
  for (int i = 1; i <= kn; i++) if (!in[i]) add(0, i);
  dfs(0); cout << f[0][m] << endl;
}