题目描述

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

思路

通过并查集判断两人是否会有交集，然后01背包

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,m,C;
const int maxn=10005;
int d[maxn],v[maxn],f[maxn],dp[maxn];
 
int find(int x)
{
	if(f[x]!=x) f[x]=find(f[x]);
	return f[x];
}
int main()
{
	int T;cin>>T;
	while(T--)
	{
		cin>>n>>m>>C;
		for(int i=1;i<=n;i++)
			f[i]=i;
		for(int i=2;i<=n;i++)
			cin>>d[i]>>v[i];
		
		int x,y;
		while(m--)
		{
			cin>>x>>y;
			int fx=find(x);
			int fy=find(y);
			f[fx]=fy;
		}
		int f1=find(1);
		memset(dp,0,sizeof dp);
		for(int i=2;i<=n;i++)
		{
			if(find(i)==f1)
			{
				for(int j=C;j>=d[i];--j)
				{
					dp[j]=max(dp[j],dp[j-d[i]]+v[i]);
				}
			}
		}
		cout<<dp[C]<<endl;
	}
	return 0;
}