C++ 搭配购买

题目描述

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

输入格式

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

第2行至 n+1n+1 行，每行有两个整数，c，dc，d，表示第 ii 朵云的价钱和价值。

第n+2n+2至 n+1+mn+1+m 行 ，每行有两个整数 u,vu,v。表示买第 uu朵云就必须买第vv朵云。同理，如果买第 vv朵就必须买第uu朵。

输出格式

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

样例输入

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

样例输出

1

code：

#include 
using namespace std;
const int maxn = 10005;
int c[maxn], d[maxn], e[maxn], f[maxn];
int ans(int x){
	if(f[x] == 0){
		return x;
	}
	return f[x] = ans(f[x]);
}
void dfs(int x, int y){
	int x1 = ans(x), y1 = ans(y);
	if(x1 != y1){
		f[y1] = x1;
		c[x1] += c[y1];
		d[x1] += d[y1];
		c[y1] = 0;
		d[y1] = 0;
	}
}
int main(){
	int n, m, w, a, b;
	cin >> n >> m >> w;
	for(int i = 1; i <= n; i++){
		cin >> c[i] >> d[i];
	}
	for(int i = 1; i <= m; i++){
		cin >> a >> b;
		dfs(a, b);
	}
	for(int i = 1; i <= n; i++)
		if(c[i] != 0)
			for(int j = w; j >= c[i]; j--) 
				e[j] = max(e[j], e[j-c[i]] + d[i]); 
			cout << e[w]; 
	return 0;
}