题解 P2014 【[CTSC1997]选课】
P2014 [CTSC1997]选课
题目大意：
给定一些点，每个点有个点权，点的访问有先后关系，若存在 \(c_{x,y}\) 即，必须先访问 \(x\) 再访问 \(y\) ，问可获得的点权最大值。
solution：
一道树上背包模板题，我们设个状态 \(f_{x,i}\) 表示以 \(x\) 为根的子树访问了 \(i\) 个点的最大点权和。设点 \(y\) 为 \(x\) 的一个儿子，那么有转移方程：
\[f_{x,j}=\max(f_{x,j},f_{y,k}+f_{x,j-k}) \]解释一下：我们现在要在 \(x\) 为根的子树中走 \(j\) 个点，我们可以在 \(y\) 的子树中选 \(k\) 个点，那么在 \(x\) 的子树中还要选 \(j-k\) 个点。注意 \(j\) 不为 \(0\) 。
细节处理：
- 添加一个虚点 \(0\) ，最后要选的点就变成了 \(m+1\) 个，方便处理也符合数据。
- 注意 \(x,y\) 的关系顺序。
代码
#include
#include
using namespace std;
const int M=1e3+5;
int m,n;
int f[M][M];
int hd[M],nt[M],to[M],cnt;
inline void tian(int x,int y){
to[++cnt]=y,nt[cnt]=hd[x],hd[x]=cnt;
}
inline void dfs(int x){
for(int i=hd[x];i;i=nt[i]){
int y=to[i]; dfs(y);
for(int j=m+1;j>=0;j--){//共m+1个点
for(int k=0;k