【BZOJ2427】[HAOI2010]软件安装（缩点+树形DP）

点此看题面

大致题意&＃xff1a; 有\(N\)个软件&＃xff0c;每个软件有至多一个依赖以及一个所占空间大小\(W_i\)&＃xff0c;只有当一个软件的直接依赖和所有的间接依赖都安装了&＃xff0c;它才能正常工作并造成\(V_i\)的价值。求在容量为\(M\)时的最大价值和。

大致思路

比较显然是树上背包。

但是&＃xff0c;这题中可能会出现环&＃xff0c;因此我们要先用\(Tarjan\)来缩点。

还要注意&＃xff0c;缩完点后的图是一个森林&＃xff0c;因此我们需要再人为建一个根&＃xff0c;将其向每棵树的根连一条边&＃xff0c;这样就可以直接树形\(DP\)了。

主要是注意细节啊。

代码

#include
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define Gmax(x,y) (x<(y)&&(x&＃61;(y)))
#define Gmin(x,y) (x>(y)&&(x&＃61;(y)))
#define abs(x) ((x)<0?-(x):(x))
#define swap(x,y) (x^&＃61;y^&＃61;x^&＃61;y)
#define uint unsigned int
#define LL long long
#define ull unsigned long long
#define INF 1000000000
#define N 100
#define M 500
#define add(x,y) (e[&＃43;&＃43;ee].nxt&＃61;lnk[x],e[lnk[x]&＃61;ee].to&＃61;y)
using namespace std;
int n,m,ee,fa[N&＃43;5],w[N&＃43;5],v[N&＃43;5],lnk[N&＃43;5],deg[N&＃43;5];
struct edge
{int to,nxt;
}e[N&＃43;5];
class Class_FIO
{private:#define Fsize 100000#define tc() (A&＃61;&＃61;B&&(B&＃61;(A&＃61;Fin)&＃43;fread(Fin,1,Fsize,stdin),A&＃61;&＃61;B)?EOF:*A&＃43;&＃43;)#define pc(ch) (void)(FoutSize}F;
class Class_Tarjan//Tarjan缩点
{private:int d,Top,dfn[N&＃43;5],low[N&＃43;5],Stack[N&＃43;5],InStack[N&＃43;5];public:int cnt,col[N&＃43;5],Weight[N&＃43;5],Val[N&＃43;5];inline bool Vis(int x) {return dfn[x];}inline void Solve(int x,int lst&＃61;0){register int i;for(dfn[x]&＃61;low[x]&＃61;&＃43;&＃43;d,InStack[Stack[&＃43;&＃43;Top]&＃61;x]&＃61;1,i&＃61;lnk[x];i;i&＃61;e[i].nxt){if(!dfn[e[i].to]) Solve(e[i].to,x),Gmin(low[x],low[e[i].to]);else if(InStack[e[i].to]) Gmin(low[x],dfn[e[i].to]);}if(dfn[x]^low[x]) return;Weight[col[x]&＃61;&＃43;&＃43;cnt]&＃61;w[x],Val[cnt]&＃61;v[x],InStack[x]&＃61;0;while(Stack[Top]^x) Weight[col[Stack[Top]]&＃61;cnt]&＃43;&＃61;w[Stack[Top]],Val[cnt]&＃43;&＃61;v[Stack[Top]],InStack[Stack[Top--]]&＃61;0;--Top;}inline void ReBuild()//重新建图{register int i;for(ee&＃61;0,i&＃61;1;i<&＃61;n;&＃43;&＃43;i) lnk[i]&＃61;0;//清空原先的边for(i&＃61;1;i<&＃61;n;&＃43;&＃43;i) col[fa[i]]^col[i]&&(add(col[fa[i]],col[i]),&＃43;&＃43;deg[col[i]]);//建新边for(i&＃61;1;i<&＃61;cnt;&＃43;&＃43;i) !deg[i]&&add(0,i);//将0号节点向每棵树的根连一条边}
}T;
class Class_TreeDP//树形DP求解树上背包
{private:int f[N&＃43;5][M&＃43;5],g[N&＃43;5];inline void DP(int x){register int i,j,k,lim;for(i&＃61;g[x]&＃61;T.Weight[x];i<&＃61;m;&＃43;&＃43;i) f[x][i]&＃61;T.Val[x];for(i&＃61;lnk[x];i;i&＃61;e[i].nxt) for(DP(e[i].to),g[x]&＃43;&＃61;g[e[i].to],j&＃61;min(m,g[x]);j>&＃61;T.Weight[x];--j)for(k&＃61;1,lim&＃61;min(j-T.Weight[x],g[e[i].to]);k<&＃61;lim;&＃43;&＃43;k) Gmax(f[x][j],f[x][j-k]&＃43;f[e[i].to][k]);}public:inline void Solve() {DP(0),F.write(f[0][m]);}
}TreeDP;
int main()
{register int i;for(F.read(n),F.read(m),i&＃61;1;i<&＃61;n;&＃43;&＃43;i) F.read(w[i]);for(i&＃61;1;i<&＃61;n;&＃43;&＃43;i) F.read(v[i]);for(i&＃61;1;i<&＃61;n;&＃43;&＃43;i) F.read(fa[i]),fa[i]&&add(fa[i],i);for(i&＃61;1;i<&＃61;n;&＃43;&＃43;i) if(!T.Vis(i)) T.Solve(i);return T.ReBuild(),TreeDP.Solve(),F.clear(),0;
}