企业官网建设流程全解析

P1455 搭配购买

网页链接

P1455 搭配购买

题目描述

明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有n nn朵云，云朵已经被老板编号为1 , 2 , 3 , . . . , n 1,2,3,...,n1,2,3,...,n，并且每朵云都有一个价值，但是商店的老板是个很奇怪的人，他会告诉你一些云朵要搭配起来买才卖，也就是说买一朵云则与这朵云有搭配的云都要买，电脑组的你觉得这礼物实在是太新奇了，但是你的钱是有限的，所以你肯定是想用现有的钱买到尽量多价值的云。

输入格式

第一行输入三个整数，n , m , w n,m,wn,m,w，表示有n nn朵云，m mm个搭配和你现有的钱的数目。

第二行至n + 1 n+1n+1行，每行有两个整数，c i , d i c_i,d_ici​,di​，表示第i ii朵云的价钱和价值。

第n + 2 n+2n+2至n + 1 + m n+1+mn+1+m行 ，每行有两个整数u i , v i u_i,v_iui​,vi​。表示买第u i u_iui​朵云就必须买第v i v_ivi​朵云,同理，如果买第v i v_ivi​朵就必须买第u i u_iui​朵。

输出格式

一行，表示可以获得的最大价值。

输入输出样例 #1

输入 #1

5 3 10 3 10 3 10 3 10 5 100 10 1 1 3 3 2 4 2

输出 #1

1

说明/提示

• 对于30 % 30\%30%的数据，满足1 ≤ n ≤ 100 1 \le n \le 1001≤n≤100；
• 对于50 % 50\%50%的数据，满足1 ≤ n , w , c i , d i ≤ 10 3 1 \le n, w,c_i,d_i \le 10^31≤n,w,ci​,di​≤103，1 ≤ m ≤ 100 1 \le m \le 1001≤m≤100；
• 对于100 % 100\%100%的数据，满足1 ≤ n , w , c i , d i ≤ 10 4 1 \le n, w,c_i,d_i \le 10^41≤n,w,ci​,di​≤104，0 ≤ m ≤ 5 × 10 3 0 \le m \le 5 \times 10^30≤m≤5×103。

解题思路

本题是并查集 + 01背包的经典组合应用题，核心是将强制捆绑购买的云朵通过并查集合并为独立物品组，再转化为经典01背包问题求解预算内的最大价值。

1. 模型转化：捆绑关系对应连通分量

搭配关系是无向的等价关系，具有传递性：若a必须和b一起买，b必须和c一起买，则a、b、c三者必须整体购买。因此可以用并查集将所有连通的云朵划分为若干个连通分量，每个连通分量作为一个不可拆分的“物品”：

• 物品重量 = 分量内所有云朵的价格之和
• 物品价值 = 分量内所有云朵的价值之和

问题最终转化为：有tot个物品，背包容量为w，每个物品只能选一次，求能装入的最大价值，即标准01背包问题。

2. 并查集处理连通分量

• 初始化：每个云朵为独立集合，父节点指向自己，同时记录自身的价格与价值。
• 合并操作：遍历所有搭配关系，合并两个云朵所在的集合。合并时将一个集合的总价格、总价值累加到另一个集合的根节点上，保证根节点存储整个分量的汇总信息。
• 收集物品：遍历所有云朵，筛选出所有根节点，将每个根对应的总价格、总价值作为一个独立物品，存入背包的物品列表。

3. 01背包求解最大价值

• 状态定义：f[j]表示花费不超过j元时能获得的最大价值，初始全为0。
• 状态转移：对每个物品，倒序遍历背包容量（从w到物品价格），执行转移：
  f [ j ] = max ⁡ ( f [ j ] , f [ j − 物品价格 ] + 物品价值 ) f[j] = \max(f[j],\ f[j - 物品价格] + 物品价值)f[j]=max(f[j],f[j−物品价格]+物品价值)
  倒序遍历是为了保证每个物品仅被选取一次，避免重复选取同一分量。
• 最终结果：f[w]即为预算w内能获得的最大价值。

算法总时间复杂度为O ( n + m + t o t × w ) O(n + m + tot \times w)O(n+m+tot×w)，其中tot为连通分量总数，完全适配题目数据规模。

总结

核心逻辑：通过并查集将捆绑购买的云朵合并为独立物品，将问题转化为标准01背包，通过一维倒序DP求解预算内的最大价值。
关键操作：并查集路径压缩与合并累加、连通分量物品收集、01背包一维空间优化与倒序转移。
效率保障：并查集接近线性复杂度，背包部分为标准01背包运算量，万级数据规模可在1秒内完成。

代码简要说明

1. 全局变量：p、v数组存储单朵云的价格与价值，fa为并查集父节点数组，np、nv存储合并后每个物品的总价格与总价值，f为背包DP数组，tot统计合并后的物品总数。
2. getfather函数：带路径压缩的并查集查找，递归更新父节点为根，大幅提升后续查询效率。
3. hb函数：合并两个集合，先查找两个节点的根；若根不同则将fy集合并入fx，同时将fy的总价格、总价值累加到fx上。
4. work函数：执行01背包动态规划，外层遍历所有物品，内层从w到物品价格倒序遍历背包容量，更新dp数组的最大值，最后输出f[w]。
5. 主函数逻辑：
   • 读入n、m、w，依次读入每朵云的价格与价值，初始化并查集父节点。
   • 读入m条搭配边，调用合并函数处理连通关系。
   • 遍历所有云朵，收集所有根节点对应的总价格、总价值，存入新物品数组。
   • 调用背包函数计算并输出结果。
6. 输入优化：关闭流同步并解绑tie，提升输入输出速度。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll n,m,w,tot;ll p[10010],v[10010],np[10010],nv[10010],f[10010],fa[10010];voidwork(){for(ll i=1;i<=tot;i++)for(ll j=w;j>=np[i];j--)f[j]=max(f[j],f[j-np[i]]+nv[i]);cout<<f[w];}llgetfather(ll x){if(fa[x]==x)returnx;fa[x]=getfather(fa[x]);returnfa[x];}voidhb(ll x,ll y){ll fx=getfather(x);ll fy=getfather(y);if(fx!=fy){v[fx]+=v[fy];p[fx]+=p[fy];fa[fy]=fx;}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m>>w;for(ll i=1;i<=n;i++){cin>>p[i]>>v[i];fa[i]=i;}for(ll i=1;i<=m;i++){ll x,y;cin>>x>>y;hb(x,y);}for(ll i=1;i<=n;i++)if(fa[i]==i){np[++tot]=p[i];nv[tot]=v[i];}work();return0;}