@[Quartz_Y](/user/275373) 用的是并查集+dp
by Mayoker @ 2022-08-11 16:23:25
@[Quartz_Y](/user/275373) 感觉合并有些奇怪,改了一下,AC了
```cpp
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
const ll N=1e4+10;
ll n,m,w;
ll f[N],val[N],dp[N],s[N];
int find(int k){
if(f[k]==k) return k;
return f[k]=find(f[k]);
}
void hb(int x,int y){
x=find(x),y=find(y);
if(x==y) return ;
f[y]=x;
// val[x]+=val[y];
// s[x]+=s[y];
}
int main(){
cin>>n>>m>>w;
for(int i=1;i<=n;i++)
cin>>s[i]>>val[i],f[i]=i;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
hb(a,b);
}
for(int i = 1; i <= n; i++)
{
int tem = find(i);
if(tem != i)
{
val[tem] += val[i];
s[tem] += s[i];
val[i] = s[i] = 0;
}
}
for(int i=1;i<=n;i++)
for(int j=w;j>=s[i];j--)
dp[j]=max(dp[j],dp[j-s[i]]+val[i]);
cout<<dp[w];
return 0;
}
```
by cmaths @ 2022-08-11 16:51:44
@[xjr300098](/user/300098) 十分感谢Orz!
by Mayoker @ 2022-08-11 17:05:25