AcWing 1252. 搭配购买
原题链接
简单
作者:
京扈
,
2023-03-23 20:15:16
,
所有人可见
,
阅读 120
#include <bits/stdc++.h>
using namespace std;
int n,m,k;
const int N=10010;
int v[N],w[N];
int p[N],dp[N];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>n>>k>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
p[i]=i;
}
while(k--)
{
int a,b;
cin>>a>>b;
a=find(a);
b=find(b);
if(a!=b) p[a]=b;
}
for(int i=1;i<=n;i++)
{
int x=find(i);
if(x!=i)
{
v[x]+=v[i];
w[x]+=w[i];
}
}
for(int i=1;i<=n;i++)
{
if(p[i]!=i) continue;
for(int j=m;j>=v[i];j--)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
cout<<dp[m]<<endl;
return 0;
}