题目就是树上背包,但要先缩点为DAG
#include <iostream> #include <cstring> #include <vector> #include <stack> using namespace std ; const int N=503,M=1003; //#define int long long #define inf 1e9 int n,m,in[N],w[N],v[N]; int pool,low[N],dfn[N]; int cl,col[N]; int W[N],VAL[N]; int f[N][M]; vector<int> g[N],graph[N]; stack<int> st; void tarjan(int x){ st.push(x); dfn[x]=low[x]=++pool; int i,y; for(i=0;i<g[x].size();i++){ y=g[x][i]; if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]); else if(!col[y]) low[x]=min(low[x],dfn[y]); } if(dfn[x]==low[x]){ cl++; do{ y=st.top(); st.pop(); col[y]=cl; }while(x!=y); } } void dp(int x){ for(int i=0;i<=m;i++){ if(i>=W[x]) f[x][i]= VAL[x]; else f[x][i]= -inf; } int j,k; for(int i=0,y;i<graph[x].size();i++){ y=graph[x][i]; dp(y); for(j=m;j>=0;j--) for(k=0;k<=j;k++) f[x][j]=max(f[x][j], f[x][j-k]+f[y][k]); } } signed main(){ int i,j,x,y; cin>>n>>m; for(i=1;i<=n;i++) cin>>w[i]; for(i=1;i<=n;i++) cin>>v[i]; for(i=1;i<=n;i++){ cin>>y; if(y) g[y].push_back(i); } for(i=1;i<=n;i++) if(!dfn[i]) tarjan(i); for(i=1;i<=n;i++) W[col[i]]+=w[i],VAL[col[i]]+=v[i]; for(i=1;i<=n;i++) for(j=0;j<g[i].size();j++){ x=col[i],y=col[g[i][j]]; if(x!=y){ in[y]++; graph[x].push_back(y); } } for(i=1;i<=cl;i++) if(in[i]==0) graph[0].push_back(i); dp(0); cout<<f[0][m]; }
标签:P2515,long,int,dfn,HAOI2010,软件,inf,include From: https://www.cnblogs.com/towboa/p/17237174.html