P1455 搭配购买【洛谷算法习题】

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 n1n1行每行有两个整数c i , d i c_i,d_ici​,di​表示第i ii朵云的价钱和价值。第n 2 n2n2至n 1 m n1mn1m行 每行有两个整数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输入 #15 3 10 3 10 3 10 3 10 5 100 10 1 1 3 3 2 4 2输出 #11说明/提示对于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​≤1031 ≤ 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​≤1040 ≤ 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(nmtot×w)其中tot为连通分量总数完全适配题目数据规模。总结核心逻辑通过并查集将捆绑购买的云朵合并为独立物品将问题转化为标准01背包通过一维倒序DP求解预算内的最大价值。关键操作并查集路径压缩与合并累加、连通分量物品收集、01背包一维空间优化与倒序转移。效率保障并查集接近线性复杂度背包部分为标准01背包运算量万级数据规模可在1秒内完成。代码简要说明全局变量p、v数组存储单朵云的价格与价值fa为并查集父节点数组np、nv存储合并后每个物品的总价格与总价值f为背包DP数组tot统计合并后的物品总数。getfather函数带路径压缩的并查集查找递归更新父节点为根大幅提升后续查询效率。hb函数合并两个集合先查找两个节点的根若根不同则将fy集合并入fx同时将fy的总价格、总价值累加到fx上。work函数执行01背包动态规划外层遍历所有物品内层从w到物品价格倒序遍历背包容量更新dp数组的最大值最后输出f[w]。主函数逻辑读入n、m、w依次读入每朵云的价格与价值初始化并查集父节点。读入m条搭配边调用合并函数处理连通关系。遍历所有云朵收集所有根节点对应的总价格、总价值存入新物品数组。调用背包函数计算并输出结果。输入优化关闭流同步并解绑tie提升输入输出速度。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n,m,w,tot;ll p[10010],v[10010],np[10010],nv[10010],f[10010],fa[10010];voidwork(){for(ll i1;itot;i)for(ll jw;jnp[i];j--)f[j]max(f[j],f[j-np[i]]nv[i]);coutf[w];}llgetfather(ll x){if(fa[x]x)returnx;fa[x]getfather(fa[x]);returnfa[x];}voidhb(ll x,ll y){ll fxgetfather(x);ll fygetfather(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);cinnmw;for(ll i1;in;i){cinp[i]v[i];fa[i]i;}for(ll i1;im;i){ll x,y;cinxy;hb(x,y);}for(ll i1;in;i)if(fa[i]i){np[tot]p[i];nv[tot]v[i];}work();return0;}