1387：搭配购买(buy)

1. //示例代码
2. #include <iostream>
3. #include <cstdio>
4. using namespace std;
5. const int N=10005;
6. int n,m,w;
7. int p,f[N],c[N],d[N],val[N];
8. int u,v;
9. 
10. // 并查集的查找函数，返回x号元素所在集合的根
11. int find(int x){
12. // 如果当前元素为其所在集合的根，则返回该元素
13.   if(f[x]==x) return f[x];
14. // 否则通过递归寻找该元素所在集合的根并路径压缩
15.   return f[x]=find(f[x]);
16. }
17. 
18. int main(){
19.   scanf("%d %d %d",&n,&m,&w);
20. // 输入n个云朵的属性之后，初始化并查集f，并对每个云朵作为单独的集合分别记录代价和价值
21. for(int i=1;i<=n;i++){
22.     scanf("%d %d",&c[i],&d[i]);
23.     f[i]=i;
24.   }
25. // 输入m个搭配方案，将相互依赖关系形成的云朵看做一个整体，使用并查集来实现
26.   for(int i=1;i<=m;i++){
27.     scanf("%d %d",&u,&v);
28. // 查找两个云朵所在集合的根节点
29.     int fu=find(u);
30.     int fv=find(v);
31.     if(fu!=fv){
32.       // 如果两个云朵不在同一个集合中，则合并它们所在的集合
33.       f[fv]=fu;
34. // 将搭配方案所包含的云朵的代价和价值累加到一个整体中
35.       c[fu]+=c[fv];
36.       d[fu]+=d[fv];
37.     }
38.   }
39. // 将并查集中的每一个集合看做一个物品，该物品的代价为搭配方案中所有云朵的代价之和，价值同理
40.   p=0;
41.   for(int i=1;i<=n;i++)
42.     if(f[i]==i){
43.       c[++p]=c[i];
44.       d[p]=d[i];
45.     }
46. // 使用01背包算法求解在购买代价不超过w的情况下可获得的最大价值
47.   for(int i=1;i<=p;i++)
48.     for(int j=w;j>=c[i];j--)
49.       val[j]=max(val[j],val[j-c[i]]+d[i]);
50.   printf("%d",val[w]);
51. return 0;
52. }