题目描述
小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;
}