BZOJ传送门
根据题目可以构造一幅图，可以得知这个图是一些森林和环，我们对图缩点，建立虚结点，使所有没有入度的强连通分量连接虚结点，再进行树上背包即可。
(相关树形背包解法)
17.8.13: 重写了一发
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100 + 5, MAXM = 500 + 5;
int n, m, wi[MAXN], vi[MAXN];
vector<int> G[MAXN], RG[MAXN];
stack<int> s;
int tb, low[MAXN], dn[MAXN], vis[MAXN], scc_size, scc_wi[MAXN], scc_vi[MAXN], scc_belong[MAXN], scc_ind[MAXN];
int dp[MAXN][MAXM];
void tarjan(int u) {
low[u] = dn[u] = ++tb;
vis[u] = -1 ,s.push(u);
for (int i=0;i<G[u].size();i++) {
int v = G[u][i];
if (!vis[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if (vis[v] == -1) low[u] = min(low[u], dn[v]);
}
if (low[u] == dn[u]) {
int e;
scc_size++;
do {
e = s.top(); s.pop();
scc_wi[scc_size] += wi[e];
scc_vi[scc_size] += vi[e];
scc_belong[e] = scc_size;
vis[e] = 1;
} while (e != u);
}
}
void dfs(int u) {
for (int i=0;i<RG[u].size();i++) {
int v = RG[u][i];
dfs(v);
for (int j=m-scc_wi[u];j>=0;j--) {
for (int k=0;k<=j;k++) {
dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
}
}
}
for (int j=m;j>=0;j--) {
if (j >= scc_wi[u]) dp[u][j] = dp[u][j - scc_wi[u]] + scc_vi[u];
else dp[u][j] = 0;
}
}
void clean() {
ms(scc_ind, 0), ms(dp, 0);
wi[0] = vi[0] = tb = scc_size = 0;
for (int i=0;i<=n;i++) vis[i] = scc_belong[i] = scc_wi[i] = scc_vi[i] = 0, G[i].clear(), RG[i].clear();
}
void solve() {
clean();
for (int i=1;i<=n;i++) scanf("%d", &wi[i]);
for (int i=1;i<=n;i++) scanf("%d", &vi[i]);
for (int i=1;i<=n;i++) {
int x; scanf("%d", &x);
G[x].push_back(i);
}
for (int i=0;i<=n;i++) if (!vis[i]) tarjan(i);
for (int u=0;u<=n;u++) {
for (int i=0;i<G[u].size();i++) {
int v = G[u][i];
if (scc_belong[u] != scc_belong[v]) RG[scc_belong[u]].push_back(scc_belong[v]), scc_ind[scc_belong[v]]++;
}
}
for (int i=1;i<=scc_size;i++) if (scc_ind[i] == 0 && i != scc_belong[0]) RG[scc_belong[0]].push_back(i);//不可以不加，即使在前面已经连上了0。如果一个图就是一个环，缩点之后0是无法到达这个点的，即di里没有0
dfs(scc_belong[0]);
printf("%d\n", dp[scc_belong[0]][m]);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%d%d", &n, &m), solve();
return 0;
}
旧：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<stack>
#define ms(i,j) memset(i,j, sizeof i);
using namespace std;
const int MAXN = 100 + 5, MAXM = 500 + 5;
int n,m;
int wi[MAXN], vi[MAXN];
vector<int> G[MAXN];
int s_size = 0, s_no[MAXN], s_wi[MAXN], s_vi[MAXN], ino[MAXN];
vector<int> RG[MAXN];
stack<int> s;
int ex[MAXN], sz = 0, dn[MAXN], low[MAXN];
void tarjan(int u)
{
dn[u] = low[u] = ++sz;
ex[u] = -1;
s.push(u);
for (int i=0;i<G[u].size();i++)
{
int v = G[u][i];
if (!ex[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (ex[v]==-1)
{
low[u] = min(low[u], dn[v]);
}
}
if (low[u]==dn[u])
{
s_size++;
int e;
do
{
e = s.top(); s.pop();
s_no[e] = s_size;
s_wi[s_size] += wi[e];
s_vi[s_size] += vi[e];
ex[e] = 1;
} while(e!=u);
}
}
void rebuild()
{
ms(ino,0);
for (int u=0;u<=n;u++)
{
for (int j=0;j<G[u].size();j++)
{
int v = G[u][j];
if (s_no[v]!=s_no[u])
{
RG[s_no[u]].push_back(s_no[v]);
ino[s_no[v]]++;
}
}
}
for (int i=1;i<=s_size;i++)
if (!ino[i]&&s_no[0]!=i) RG[s_no[0]].push_back(i);
}
int f[MAXN][MAXM];
void dp(int u)
{
for (int i=0;i<RG[u].size();i++)
{
int v = RG[u][i];
if (!ex[v])
{
ex[v] = true;
dp(v);
for (int j=m-s_wi[u];j>=0;j--)
for (int k=0;k<=j;k++)
f[u][j] = max(f[u][j], f[u][j-k]+f[v][k]);
}
}
for (int j=m;j>=0;j--)
{
if (j>=s_wi[u]) f[u][j] = f[u][j-s_wi[u]] + s_vi[u];
else f[u][j] = 0;
}
}
int main()
{
scanf("%d%d", &n,&m); wi[0] = vi[0] = 0;
for (int i=1;i<=n;i++) scanf("%d", &wi[i]);
for (int i=1;i<=n;i++) scanf("%d", &vi[i]);
for (int i=1;i<=n;i++)
{
int di;
scanf("%d", &di);
G[di].push_back(i);
}
ms(ex,0); ms(s_wi,0); ms(s_vi,0);
for (int i=0;i<=n;i++) if (!ex[i]) tarjan(i);
rebuild();
ms(ex,0); ms(f,0); dp(s_no[0]);
printf("%d\n", f[s_no[0]][m]);
return 0;
}
