# 11613: 【原1613】Interesting Knapsack

### 题目描述

author: xzj 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1613

## Sample Input 1

``````5 5
0 1 2
0 2 3
0 3 5
0 4 4
0 5 7
``````

## Sample Output 1

``````8
``````

## Sample Input 2

``````5 5
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1000
``````

## Sample Output 2

``````5
``````

## Data

• 对于30％的数据，满足 N<=18（该部分其中一半数据，全部的物品Fi=0）;
• 对于另外30％的数据，满足 N<=1000（全部的物品Fi=0）;
• 对于另外20％的数据，满足 N<=100；
• 对于100％的数据，满足 N<=1000.
• W与N数据范围一致。
• Wi，Vi全部为非负整数，答案在int以内.

## zqy2018's solution

``````/*
See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu1613.md
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, W;
int f[1005], w[1005], v[1005];
int lis[1005], lis_len = 0;
int dp[1005][8005] = {0};
int to[1005], at[1005] = {0}, nxt[1005], cnt = 0;
int du[1005] = {0};
int tim[1005], D = 0, siz[1005] = {0};
void ddfs(int cur){
siz[cur] = 1;
for (int i = at[cur]; i; i = nxt[i])
ddfs(to[i]), siz[cur] += siz[to[i]];
tim[++D] = cur;
}
void init(){
for (int i = 1; i <= n; ++i){
if (f[i] > 0)
to[++cnt] = i, nxt[cnt] = at[f[i]], at[f[i]] = cnt, ++du[i];
}
w[n + 1] = v[n + 1] = 0;
for (int i = 1; i <= n; ++i){
if (du[i]) continue;
if (at[i] > 0){
to[++cnt] = i, nxt[cnt] = at[n + 1], at[n + 1] = cnt;
}else {
lis[++lis_len] = i;
}
}
ddfs(n + 1);
}
void solve(){
for (int i = 1; i <= D; ++i){
int iid = tim[i];
int ww = w[iid], vv = v[iid];
for (int j = 0; j <= W; ++j){
int cdt = dp[i - siz[iid]][j];
if (j >= ww) cdt = max(cdt, dp[i - 1][j - ww] + vv);
dp[i][j] = cdt;
}
}
for (int i = 1; i <= lis_len; ++i){
int ww = w[lis[i]], vv = v[lis[i]];
for (int j = W; j >= ww; --j)
dp[D][j] = max(dp[D][j], dp[D][j - ww] + vv);
}
printf("%d\n", dp[D][W]);
}
int main(){
init();
solve();
return 0;
}
``````