这是AC代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, m, w, c[N], d[N], u, v, fa[N], a[N][3], idx, f[N], ans;
int find(int x){
while(x != fa[x])
x = fa[x] = fa[fa[x]];
}
pair<int, int> p[N];
int main(){
scanf("%d%d%d", &n, &m ,&w);
for(int i = 1; i <= n; i ++)
fa[i] = i;
for(int i = 1; i <= n; i ++){
scanf("%d%d", &c[i], &d[i]);
}
for(int i = 1; i <= m; i ++){
scanf("%d%d", &u, &v);
fa[find(u)] = find(v);
}
for(int i = 1; i <= n; i ++)
p[i].first = find(i), p[i].second = i;
sort(p + 1, p + 1 + n);
p[0].first = 0;
for(int i = 1; i <= n; i ++){
if(p[i].first != p[i - 1].first){
idx ++;
a[idx][1] += d[p[i].second];
a[idx][2] += c[p[i].second];
}
else{
a[idx][1] += d[p[i].second];
a[idx][2] += c[p[i].second];
}
}
n = idx;
// printf("\n");
// for(int i = 1; i <= n; i ++)
// printf("%d %d\n", a[i][1], a[i][2]);
for(int i = 1; i <= n; i ++){
for(int j = w; j >= a[i][2]; j --)
f[j] = max(f[j], f[j - a[i][2]] + a[i][1]);
}
for(int i = 1; i <= w; i ++)
ans = max(ans, f[i]);
printf("%d", ans);
return 0;
}
//1 价值 2 价格
注意看,find函数内并没有
return x;
但最终还是AC,这是什么神奇的数据???