搭配购买——并查集+01背包（洛谷P1455）土豆片的算法之路

在期末周的摧残之下，土豆片依然没有忘记自己的算法学习（虽然是为了搞钱跟椒盐粉出去玩）来看看这周的并查集专题。

基础知识：?

“并查集的意义”

何为“并查集？”简单来说，就是将数据分为几个不相交小组（集合），确定每个小组的组长，可以进行查询（查找此元素所处小组以及组长，可用于判断两元素是否同属一个小组），合并（将两不相交小组合并为一个小组）。

其中最重要的就是使用find（）与unit（）函数来实现这两个功能。

并查集查询实现——find（）函数

我们定义一个数组boss用来记录每个人的上级是谁（就像土豆片的老大是椒盐粉/(ㄒoㄒ)/~~），例如boss[10]=13;就表示10号的上级是13号，若一个人的上级是他本身，那就代表他是组长了（也可能是自己一个人一个小组）

int find(int x){				//查找x的上级
	while(boss[x]!=x){			//如果x的上级不是自己则说明找到的人不是组长
		x=boss[x];
    }				//继续找上级，直到找到组长为止
	return x;					
}

更优的做法是将x到根节点路径上的所有点的boss（上级）都设为根节点，用人话说应该就是，所有人只有一个老大就是组长。

int find(int x)     				//查找结点x的根结点(组长)
{
    if(boss[x]==x) return x;		//x的上级为x本身,即x为根结点        
    return boss[x]=find(boss[x]);	//此代码相当于先找到根结点，然后pre[x]=组长 
}

并查集合并实现——unit（）函数?

unit函数的作用是将两个不相交集合合并，道理大家肯定都懂（连土豆片都明白）但是该如何实现，最简单的就是——直接让其中一个组长认另一个组长为老大就可以直接实现将两个小组合并（就像是被吞并？）unit（）函数的作用就是个这。

unit（）函数的逻辑：

1、寻找 x的组长
2、寻找 y的组长
3、如果 x 和 y 不相等，则随便选一个人作为另一个人的上级，如此一来就完成了两个组的合并。

void unit(int x,int y)                     
{
    int fx=find(x),fy=find(y);           //找x，y的老大
    if(fx!=fy)                          //x，y的老大不是同一个人
        pre[fx]=fy;                        //让x的老大认y组长为老大
}

以上就是并查集的简单知识，详细的可以看看大佬文章链接

例题（并查集与01背包）：

板子题土豆片就不在这里多说了，正好遇见了这题与上周的背包专题结合题目链接

题目：

题目描述：

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

输入格式：

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

第二行至 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

思路 ：

这是一道并查集+01背包题，01背包的限制条件为买A必须买B，故可以用并查集将几个物品合成一个大物品，大物品的价值即为几个物品价值的和，然后再用01背包做即可。

代码实现：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,w,num;
int money[1000003],val[1000005],newmoney[1000006],newval[1000002],f[1000005],per[1000004];

int findd(int x){	//找老大啊找老大 
	if(per[x]==x){
		return x;
	}else{
		return per[x]=findd(per[x]);
	}
}

void unit(int x,int y){
	int fx=findd(x);		//将捆绑销售的合并为一个大物品  
	int fy=findd(y);
	if(fx!=fy) {
		val[fx]+=val[fy];
		money[fx]+=money[fy];
		per[fy]=fx;
	}
}

signed main(){
	cin>>n>>m>>w;
	int c,d;
	for(int i=1; i<=n;i++){
		cin>>c>>d;
		money[i]=c;
		newval[i]=d;		//存价值，价格 
		per[i]=i;	//初始化数组 
	}
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		unit(x,y);		//联合 
	}
	for(int i=1;i<=n;i++){																																																									//土豆片最帅！！ 
		if(per[i]==i){
			newmoney[++num]=money[i];	//大物品的花费 
			newval[num]=newval[i];	//大物品的价值 
		} 
	}
	for(int i=1;i<=num;i++){
		for(int j=w;j>=newmoney[i];j--){
			f[j]=max(f[j],f[j-newmoney[i]]+newval[i]);	//01背包 
		}		
	}
	cout<<f[w];
}

??完结撒花*★,°*:.☆(￣▽￣)/$:*.°★* 。