@[involutionKing](/user/529679)
改了一点小问题 还有一个点过不了你看看
```cpp
/*[in]
20 10 100
31 42
14 58
27 3
19 66
38 76
27 93
37 82
45 78
28 79
25 80
8 85
44 49
12 79
35 7
45 2
4 77
12 94
3 29
26 71
46 92
17 1
8 19
14 12
4 11
12 15
19 10
4 7
17 14
3 6
17 13
[out]
418
*/
//这个点过不了
#include<bits/stdc++.h>
#define maxn 10005
using namespace std;
int n, m, w, i, j, c[maxn], d[maxn], f[maxn], dp[maxn];
int find(int x){
if(f[x]!=x){
f[x] = find(f[x]);
}
return f[x];
}
void add(int rr1, int rr2){
int r1 = find(rr1);
int r2 = find(rr2);
if(r1!=r2){
f[r1] = r2;
}
}
int main(){
cin>>n>>m>>w;
for(i=1;i<=n;i++){
cin>>c[i]>>d[i];
f[i] = i;
}
for(i=1;i<=m;i++){
int u, v;
cin>>u>>v;
c[v] += c[u];
c[u] = 0;
d[v] += d[u];
d[u] = 0;
add(u, v);
}
for(i=1;i<=n;i++){
// f[i]!=i意思是这件商品不存在
if(f[i]!=i){
continue;
}
//cout<<"i="<<i<<" 价格:"<<c[i]<<" 价值:"<<d[i]<<endl;
for(j=w;j>=c[i];j--){
dp[j] = max(dp[j] , dp[j-c[i]] + d[i]);
}
}
cout<<dp[w];
return 0;
}
```
by LIUYC_C @ 2023-04-04 16:57:32
@[involutionKing](/user/529679) 很显然吧,你价值和重量得在祖先上加的,不单单合并。
by Loser_Syx @ 2023-06-06 15:55:46