链接：https://ac.nowcoder.com/acm/contest/24/D
来源：牛客网
 

题目描述

小d是一个搞房地产的土豪。每个人经商都有每个人经商的手段，当然人际关系是需要放在首位的。
小d每一个月都需要列出来一个人际关系表，表示他们搞房地产的人的一个人际关系网，但是他的精力有限，对应他只能和能够接触到的人交际。比如1认识2,2认识3，那么1就可以接触3进行交际，当然1和2也可以交际。
小d还很精明，他知道他和谁交际的深获得的利益大，接下来他根据自己的想法又列出来一个利益表，表示他和这些人交际需要耗用多少精力，能够获得的利益值为多少。
小d想知道，他在精力范围内，能够获得的利益值到底是多少。
设定小d自己的编号为1.并且对应一个人的交际次数限定为1.

输入描述:

本题包含多组输入，第一行输入一个数t，表示测试数据的组数
每组数据的第一行输入三个数，N,M，C，表示这个人际关系网一共有多少个人，关系网的关系数，以及小d的精力值
接下来N-1行，每行两个数ai，bi。这里第i行表示和编号为i+1的人认识需要花费ai的精力，能够获得的利益值为bi。
再接下来M行，每行两个数x，y，表示编号为x的人能够和编号为y的人接触
t<=50
2<=N<=10000
1<=M<=10*N
1<=ai，bi<=10
1<=C<=500
1<=x,y<=N

输出描述:

输出包含一行，表示小d能够获得的最大利益值

 

示例1

输入

复制

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

输出

复制

10

说明

小明能够接触到的人的编号有：2 3 4，那么对应接触编号为2的人花费5精力能够获得10的利益值是最优方案。

 

水题：dp+并查集，参见代码注释

//哈理工软件学院第六届ACM编程决赛-高年级组:D
//居然是个dp！！！
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e5+120;
int t;
int N;
ll M;
struct Node {
	int a;//精力
	int b;//收获
	int num;//编号
}w[maxn];
int C;//总精力
int x, y;
ll dp[maxn];//总收获
int pre[maxn];
int find(int x)
{
	if (x == pre[x])
		return x;
	return pre[x] = find(pre[x]);
}
void join(int x, int y)
{
	int fx = find(x);
	int fy = find(y);

	if (fx == fy)
		return;
	pre[fy] = fx;
}
int main()
{
	ios::sync_with_stdio(false);
	cin >> t;
	while (t--)
	{
		cin >> N >> M >> C;
		for (int i = 2; i <= N; i++) {
			cin >> w[i].a >> w[i].b;
		}
		for (int i = 0; i <= N; i++)
			pre[i] = i;
		for (int i = 1; i <= M; i++) {
			cin >> x >> y;
			join(x, y);//将编号为x的人和编号为y的人联系到一起
		}
		for (int i = 2; i <= N; i++) {//若编号为i的人和1有共同的父节点，则他们可以不用精力就联系起来
			if(find(i)==find(1))
				flag[i] = 1;
		}
		memset(dp, 0, sizeof(dp));
		for (int i = 2; i <= N; i++) {
			if (flag[i] != 1)continue;
			for (int j = C; j >= w[i].a; j--) {
				dp[j] = max(dp[j], dp[j - w[i].a] + w[i].b);//背包问题：每次的收获都是从选人或不选人转移过来
			}
		}
		cout << dp[C] << endl;
	}
	return 0;
}