蒟蒻代码求帮助
/*[in]
5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2
[out]
1
*/
#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];
d[v] += d[u];
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--){
if(dp[j-c[i]]+d[i] > dp[j]){
dp[j] = dp[j-c[i]]+d[i];
}
}
}
cout<<dp[n];
return 0;
}