1387：搭配购买(buy)
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
Joe觉得云朵很美，决定去山上的商店买一些云朵。商店里有n朵云，云朵被编号为1，2，…，n，并且每朵云都有一个价值。但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。
但是Joe的钱有限，所以他希望买的价值越多越好。
【输入】
第1行n，m，w，表示n朵云，m个搭配，Joe有w的钱。
第2~n+1行，每行ci，di表示i朵云的价钱和价值。
第n+2~n+1+m行，每行ui，vi，表示买ui就必须买vi，同理，如果买vi就必须买ui。
【输出】
一行，表示可以获得的最大价值。
【输入样例】
5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2
【输出样例】
1
【提示】
【数据范围】
30%的数据保证：n≤100；
50%的数据保证：n≤1,000；m≤100；w≤1,000；
100%的数据保证：n≤10,000；0≤m≤5000；w≤10,000。
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. }
