算法-并查集-买女装

1.题目描述

小庄是个女装爱好者，有一天他跑到女装店去买女装。商店里有编号从1到n的n件衣物饰品，每一件都有固定的魅力加成值。
老板告诉他，其中某些商品必须搭配购买，而且商品之间的搭配关系具有传递性，若A与B搭配且B与C搭配，则A与C也搭配。
小庄带的钱有限，请你帮他找到魅力加成值总和最大的购买方案。

输入
可能有多组输入。
每组输入第一行有三个数N、M、W（1<=N<=10000;0<=M<=5000,0<=W<=10000），
分别表示商店内有N件商品、老板告诉了小庄M种搭配关系、小庄带的钱数。 
接下来N行，每行有两个数Vi、Ci，分别表示第i件商品的价格和魅力加成值。
接下来M行，每行有两个数A和B，表示编号为A和B的商品必须同时购买。

输出
每组输出有一行，为最大魅力加成值。

样例输入
5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2

样例输出
1

2. 思路

     解题思路：首先识别出有联系的商品搭配关系（即找出一个个的搭配圈子），然后将每一个搭配圈里的商品的价格与魅力值进行叠加。从此可以正式将整个问题转化成了一个01背包问题，即 现有k件价值为Vi、魅力值为Ci的商品（k代表搭配圈的个数，Vi、Ci则是第i个搭配圈中商品价格与魅力值的总和），在总金额W的情况下，如何购买才能使得魅力值总和最大？

     技术路线：先用并查集区分每一个搭配圈，并且把每一件商品的价格、魅力值加到其搭配圈的根节点上，然后将每个搭配圈的根节点作为背包元素采用动态规划求解01背包问题。

3. 代码

import java.io.BufferedReader;
import java.io.InputStreamReader;public class F_买女装 {static int n, m, w, res;static int[] root;// 寻找当前搭配圈中的根节点，输入样例中的1,2,3,4都属于同一搭配圈，其根节点root[2]=0static int find(int x) {if (root[x] > 0) {x = root[x];}return x;}// 联合搭配圈的节点，使其最终指向根节点static void union(int x, int y, int[] value, int[] charm) {int rx = find(x); // 得到x所在搭配圈的根节点int ry = find(y); // 得到y所在搭配圈的根节点if (rx == ry)	//若本来就在同一个搭配圈里则不管return;root[rx] = ry;	//若不在同一圈子，那么就把x所在的圈子添加到y所在的圈子中，ry为根节点。//将新进搭配圈的商品 的价格与魅力值加到根节点上value[ry] += value[rx];	charm[ry] += charm[rx];}public static void main(String[] args) throws Exception {// TODO 自动生成的方法存根BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String line = br.readLine();n = Integer.parseInt(line.split(" ")[0]);m = Integer.parseInt(line.split(" ")[1]);w = Integer.parseInt(line.split(" ")[2]);int[] value = new int[n + 1];int[] charm = new int[n + 1];root = new int[n + 1];for (int i = 1; i <= n; i++) {line = br.readLine();value[i] = Integer.parseInt(line.split(" ")[0]);charm[i] = Integer.parseInt(line.split(" ")[1]);}// 1.构造并查集，寻找搭配圈for (int i = 1; i <= m; i++) {line = br.readLine();int a = Integer.parseInt(line.split(" ")[0]);int b = Integer.parseInt(line.split(" ")[1]);union(a, b, value, charm);}// 2.动规求解01背包问题int[] m = new int[w+1];for(int i=1;i<=n;i++){if(root[i] == 0){	//寻找根节点,每找到一个根节点就开始重新定义dp数组for(int j=w;j>=value[i];j--){m[j] = Math.max(m[j], m[j-value[i]]+charm[i]);}}}System.out.print(m[w]);}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！