BZOJ傳送門 根據題目可以構造一幅圖，可以得知這個圖是一些森林和環，我們對圖縮點，建立虛結點，使所有沒有入度的強連通分量連接虛結點，再進行樹上背包即可。
#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]);新聞熱點
疑難解答
