原代码：

#include<iostream>
#include<stdio.h>
using namespace std;
int m,n,W,x,y;
int w[10007],v[10007],fa[10007],f[10007];
int find(int ck){ return fa[ck]==ck?ck:fa[ck]=find(fa[ck]); }
int main(){
	scanf("%d%d%d",&n,&m,&W);
	for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		int a=find(x),b=find(y);
		if(a==b)continue;
		fa[x]=b;
		w[b]+=w[x];
		v[b]+=v[x];
	}
//	for(int i=1;i<=n;i++)cout<<w[i]<<" ";cout<<endl;
//	for(int i=1;i<=n;i++)cout<<v[i]<<" ";cout<<endl;
	for(int i=1;i<=n;i++){
		if(fa[i]!=i)continue;
		for(int j=W;j>=w[i];j--)
			f[j]=max(f[j],f[j-w[i]]+v[i]);
	}
	cout<<f[W];
	return 0;
}

现代码：

#include<iostream>
#include<stdio.h>
using namespace std;
int m,n,W,x,y;
int w[10007],v[10007],fa[10007],f[10007];
int find(int ck){ return fa[ck]==ck?ck:fa[ck]=find(fa[ck]); }
int main(){
	scanf("%d%d%d",&n,&m,&W);
	for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		int a=find(x),b=find(y);
		if(a==b)continue;
		fa[a]=b;
		w[b]+=w[a];
		v[b]+=v[a];
	}
//	for(int i=1;i<=n;i++)cout<<w[i]<<" ";cout<<endl;
//	for(int i=1;i<=n;i++)cout<<v[i]<<" ";cout<<endl;
	for(int i=1;i<=n;i++){
		if(fa[i]!=i)continue;
		for(int j=W;j>=w[i];j--)
			f[j]=max(f[j],f[j-w[i]]+v[i]);
	}
	cout<<f[W];
	return 0;
}

我们可以发现唯一的区别是main函数中

	fa[x]=b;
	w[b]+=w[x];
	v[b]+=v[x];

这三行改为了：

	fa[a]=b;
	w[b]+=w[a];
	v[b]+=v[a];

原因是w[x]v[x]只代表了x所在集合以x为代表节点时的价格与价值，但我们合并时x节点极有可能已被并入其他集合，所以我们在转移W与V时应当转移x所在集合的代表元素的w与v到y所在集合的代表元素上，而不是转移x这一个节点