题目大意：
有n个软件，每个软件依赖于其它至多一个软件，每个软件有一个代价w和收益v，问在总代价不超过m时，最大收益为多少。
思路：
树形DP。
f[i][j]表示第i个点，代价为j的最大收益。
设当前结点为x，一个子结点是y，其中原来已经付出的代价为i，在y处新付出的代价为j，则状态转移方程为：
f[x][i+j]=max{f[x][i]+f[y][j]};
然而这样只有30分，其实仔细审查题目发现可能有一些软件互相依赖，即构成了一个环，
而环上的软件要么都选，要么都不选，因此我们可以将其当成一个软件处理。
所以只要跑一遍Tarjan缩点即可。
再观察可以进一步发现，所有依赖关系要么构成一棵树，要么至多只有一个环。
其中0号一定是一棵树的根，而带环树上的环一定在树的最顶端。
因此方便起见我们缩点后可以将所有的连通块合并成一棵树处理。
洛谷上莫名其妙跑了Rank1，BZOJ上跑得也挺快的。
1 #include<stack> 2 #include<queue> 3 #include<cstdio> 4 #include<cctype> 5 #include<vector> 6 #include<cstring> 7 inline int getint() { 8 register char ch; 9 while(!isdigit(ch=getchar())); 10 register int x=ch^'0'; 11 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 12 return x; 13 } 14 const int N=101,M=501; 15 int w[N],v[N],d[N]; 16 std::vector<int> e[N]; 17 inline void add_edge(const int &u,const int &v) { 18 e[u].push_back(v); 19 } 20 int dfn[N],low[N],scc[N],cnt,id; 21 bool ins[N]; 22 std::stack<int> s; 23 void tarjan(const int &x) { 24 dfn[x]=low[x]=++cnt; 25 s.push(x); 26 ins[x]=true; 27 for(unsigned i=0;i<e[x].size();i++) { 28 const int &y=e[x][i]; 29 if(!dfn[y]) { 30 tarjan(y); 31 low[x]=std::min(low[x],low[y]); 32 } else if(ins[y]) { 33 low[x]=std::min(low[x],dfn[y]); 34 } 35 } 36 if(dfn[x]==low[x]) { 37 int y=-1; 38 while(y!=x) { 39 y=s.top(); 40 s.pop(); 41 ins[y]=false; 42 scc[y]=id; 43 } 44 id++; 45 } 46 } 47 int cost[N],val[N]; 48 int f[N][M]; 49 int m; 50 void dp(const int &x) { 51 if(cost[x]>m) return; 52 f[x][cost[x]]=val[x]; 53 for(unsigned i=0;i<e[x].size();i++) { 54 const int &y=e[x][i]; 55 dp(y); 56 for(register int i=m;i>=0;i--) { 57 if(!~f[x][i]) continue; 58 for(register int j=m-i;j>=0;j--) { 59 if(!~f[y][j]) continue; 60 f[x][i+j]=std::max(f[x][i+j],f[x][i]+f[y][j]); 61 } 62 } 63 } 64 } 65 int ans[M]; 66 int ind[N]; 67 int main() { 68 const int n=getint(); 69 m=getint(); 70 for(register int i=1;i<=n;i++) { 71 w[i]=getint(); 72 } 73 for(register int i=1;i<=n;i++) { 74 v[i]=getint(); 75 } 76 for(register int i=1;i<=n;i++) { 77 d[i]=getint(); 78 add_edge(d[i],i); 79 } 80 for(register int i=0;i<=n;i++) { 81 if(!dfn[i]) tarjan(i); 82 cost[scc[i]]+=w[i]; 83 val[scc[i]]+=v[i]; 84 e[i].clear(); 85 } 86 for(register int i=1;i<=n;i++) { 87 if(scc[i]==scc[d[i]]) continue; 88 add_edge(scc[d[i]],scc[i]); 89 ind[scc[i]]++; 90 } 91 for(register int i=0;i<id;i++) { 92 if(i==scc[0]||ind[i]) continue; 93 add_edge(scc[0],i); 94 } 95 memset(f,-1,sizeof f); 96 dp(scc[0]); 97 int ans=0; 98 for(register int i=0;i<=m;i++) { 99 ans=std::max(ans,f[scc[0]][i]); 100 } 101 printf("%d ",ans); 102 return 0; 103 }