【题目来源】
https://oj.czos.cn/p/1928
【题目描述】
王老师来到商店为同学们采购礼品。
这家店有 n 种礼品（编号是 1~n），每种礼品只有 1 件。老板为了促销，对礼品进行搭配销售，有关联性的礼品必须都要采购（奇怪的规定），比如 1 号礼品和 3 号礼品搭配了，3 号和 8 号礼品搭配了，那么王老师想要买 1 号礼品的话，就需要把 3 号和 8 号礼品都买了。
现给定每种礼品的价钱和价值，请问在有限的钱 w 的情况下，能够买到礼品的最大价值是多少？
【输入格式】
第一行输入三个整数，n，m，w，表示有 n 种礼品，m 个搭配和你现有的钱的数目 w。
第二行至 n+1 行，每行有两个整数，c、d，表示第 i 种礼品的价钱和价值。（1≤c,d≤10^5）
第 n+2 至 n+1+m 行，每行有两个整数，u、v，表示 u 号礼品和 v 号礼品是有关联的，已经形成搭配销售的关系。
【输出格式】
一行，表示可以获得的最大价值。
【输入样例】
5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2
【输出样例】
1
【数据范围】
1≤n,w≤10^4，0≤m≤5×10^3。
【算法分析】
● 并查集：https://blog.csdn.net/hnjzsyjyj/article/details/146948171
● 有依赖的背包（树形背包）核心是物品间存在选子必选父的单向依赖关系，依赖结构通常为森林或多叉树，主流解法为树形 DP 结合分组背包自底向上合并；若题目中是双向强依赖、互相绑定的物品组（选其一必全选），则可先用并查集将连通块缩为超级物品，再套用普通 01 背包求解，两种思路对应不同依赖模型，共同构成完整解法体系。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int N=1e4+5;
int vol[N],val[N],f[N];
int pre[N];
int n,m,V;int find(int x) {if(x!=pre[x]) pre[x]=find(pre[x]);return pre[x];
}void merge(int x,int y) {int a=find(x);int b=find(y);if(a!=b) pre[a]=b;
}int main() {cin>>n>>m>>V;for(int i=1; i<=n; i++) {cin>>vol[i]>>val[i];pre[i]=i;}for(int i=1; i<=m; i++) {int x,y;cin>>x>>y;merge(x,y);}for(int i=1; i<=n; i++) {if(pre[i]!=i) {vol[find(i)]+=vol[i];val[find(i)]+=val[i];vol[i]=0;val[i]=0;}}for(int i=1; i<=n; i++) { //0-1 bagfor(int j=V; j>=vol[i]; j--) {f[j]=max(f[j],f[j-vol[i]]+val[i]);}}cout<<f[V]<<endl;return 0;
}/*
in:
5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2out:
1
*/
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/146948171
https://mp.weixin.qq.com/s/EOk7vFnpusJism2Md4Inrw
https://blog.csdn.net/chenminggui123/article/details/141400595