明天就是母親節(jié)了，電腦組的小朋友們在忙碌的課業(yè)之余挖空心思想著該送什么禮物來表達自己的心意呢？聽說在某個網(wǎng)站上有賣云朵的，小朋友們決定一同前往去看看這種神奇的商品，這個店里有 n n n 朵云，云朵已經(jīng)被老板編號為 1 , 2 , 3 , . . . , n 1,2,3,...,n 1,2,3,...,n，并且每朵云都有一個價值，但是商店的老板是個很奇怪的人，他會告訴你一些云朵要搭配起來買才賣，也就是說買一朵云則與這朵云有搭配的云都要買，電腦組的你覺得這禮物實在是太新奇了，但是你的錢是有限的，所以你肯定是想用現(xiàn)有的錢買到盡量多價值的云。

第一行輸入三個整數(shù)， n , m , w n,m,w n,m,w，表示有 n n n 朵云， m m m 個搭配和你現(xiàn)有的錢的數(shù)目。

第二行至 n + 1 n+1 n+1 行，每行有兩個整數(shù)， c i , d i c_i,d_i ci?,di?，表示第 i i i 朵云的價錢和價值。

第 n + 2 n+2 n+2 至 n + 1 + m n+1+m n+1+m 行 ，每行有兩個整數(shù) u i , v i u_i,v_i ui?,vi?。表示買第 u i u_i ui? 朵云就必須買第 v i v_i vi? 朵云,同理，如果買第 v i v_i vi? 朵就必須買第 u i u_i ui? 朵。

一行，表示可以獲得的大價值。

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

1

• 對于 30 % 30\% 30% 的數(shù)據(jù)，滿足 1 ≤ n ≤ 100 1 \le n \le 100 1≤n≤100；
• 對于 50 % 50\% 50% 的數(shù)據(jù)，滿足 1 ≤ n , w ≤ 1 0 3 1 \le n, w \le 10^3 1≤n,w≤103， 1 ≤ m ≤ 100 1 \le m \le 100 1≤m≤100；
• 對于 100 % 100\% 100% 的數(shù)據(jù)，滿足 1 ≤ n , w ≤ 1 0 4 1 \le n, w \le 10^4 1≤n,w≤104， 0 ≤ m ≤ 5 × 1 0 3 0 \le m \le 5 \times 10^3 0≤m≤5×103。

這題的算法很簡單啊~~ 就是一個普通的01背包+并查集。
01背包和并查集想必大家一定都了如指掌，那么我就不講了，下面直接上代碼：

• 并查集文章（小天狼星自己寫的）
• 01背包文章（同上）
• 并查集資源（無需積分/C幣）

好了終于可以安心的給出代碼了👇

#include//相信不會有人不知道萬能頭吧~
using namespace std;
int v,n,m,a,b,d[20000],c[20000],w[20000],f[20000];
int fr(int x)		//查找根結(jié)點的函數(shù)
{if (x!=f[x])
		x=fr(f[x]);
	return x;
}
int main()
{cin >>n >>m >>v;
	for (int i=1;i<=n;i++)
		f[i]=i;				//初始化并查集
	for (int i=1;i<=n;i++)
		cin >>w[i] >>c[i];		//輸入價錢和價格
	for (int i=1;i<=m;i++)
	{cin >>a >>b;	//輸入要合并的兩個云朵
		f[fr(a)]=fr(b);			//合并a，b
	}
	for (int i=1;i<=n;i++)		//關(guān)鍵循環(huán)
	{int zx=fr(i);
		if (zx!=i)	//如果自己不是首領(lǐng)/祖先，說明自己的祖先是其他人
		{	w[zx]+=w[i];
			c[zx]+=c[i];	//將自己的數(shù)據(jù)加入到=祖先那里
			w[i]=1e+6;		//將自己的價格設(shè)為大值，讓小朋友買不起
		}
	}
	for (int i=1;i<=n;i++) 
		for (int j=v;j>=w[i];j--)
		{	d[j]=max(d[j],d[j-w[i]]+c[i]);		//01背包模板
		}
	cout<

好了，結(jié)束??！
這題你學會了嗎？