2025/2/7课堂记录
目录[*]二叉苹果树
[*]选课
[*]二叉苹果树
这是一道树上依赖背包题，也叫做分组背包
依赖：选这一个，从它到根所有节点都要选，具有依赖性
分组：每个节点下的子节点分好几个组，每一个组单独做背包
maketree：因为题目没告诉父子关系，要自己推
看注释！！就写了亿点点注释 #include#includeusing namespace std;int map,l,r,ap,f;int n,q;void maketree(int a){ for(int i=1;i=0)//找到啦（你的破绽，砰！ { l=i;//标记左孩子（其实也不一定，但无所谓 ap=map;//所有的苹果放在孩子身上，这步是关键思想！！！！！！！！！ map=-1;//删边 map=-1; maketree(i);//从孩子接着往下推 break;//一定要炸掉，不然l就被顶替了 } for(int i=1;i=0) { r=i; ap=map; map=-1; map=-1; maketree(i); break; }}int dp(int fa,int num)//dp(fa,num)和f的含义都是fa节点必选，总共选num个节点最多苹果数 { if(num==0)return 0;//一个都没有那就一个都没有呗 if(l==0)return ap;//没有孩子那就只有自己呗（此时num肯定>0） if(f>0)return f;//之前来过了，不用再来了 for(int i=0;i>n>>q;//n:节点数量，q：保留边数量 q++;//保留q条边，实际就是保留q+1个节点（父亲+每一条边后面跟着一个节点 memset(map,-1,sizeof(map));//初始化负数 for(int i=1;i>x>>y>>z; map=z;//因为输入的时候父亲孩子没有固定顺序 map=z;//所以双向建图就行，反正用的链接表，多余空间不用白不用 } maketree(1);//从根节点一点一点往下推 cout=1;t--) { f=f+a; } }}int main(){ cin>>m>>n; //这里并没有把树根单独拎出来的原因是把所有树根直接绑在了0上，相当于0是根，所有的“根”都是0的孩子 //把一片树林看作一颗树 for(int i=1;i>x>>y; a=y; //存储成有向图的方式 tr.push_back(i);//x是父亲，i是孩子 } dfs(0);//森林的根 cout
页:
[1]