并查集问题
查看原帖
并查集问题
180453
wangyansong楼主2020/11/17 11:01

为啥f[yy]=xx 对了 f[xx]=yy不对

#include<bits/stdc++.h>
using namespace std;
int n,m,a[10000000],dp[10000000],f[40000000];
int x,y,w,b[10000000];
int find (int k){
	while(k!=f[k])k=f[k]=find(f[k]);
	return k;
}
int main()
{
   cin>>n>>m>>w;
   for(int i=1;i<=n;i++)
    f[i]=i;
   for(int i=1;i<=n;i++){
   scanf("%d%d",&a[i],&b[i]);
   }
   for(int i=1;i<=m;i++){
   	scanf("%d%d",&x,&y);
   	int xx=find(x),yy=find(y);
   	if(xx==yy) continue;
   	if(x==y) continue;
   	f[yy]=xx;
   	a[xx]+=a[yy],a[yy]+=a[xx];
   	b[xx]+=b[yy];b[yy]+=b[xx];
   }
    for(int i=1;i<=n;i++){
    	if(f[i]==i)
	for(int j=w;j>=a[i];j--)
    dp[j]=max(dp[j],dp[j-a[i]]+b[i]);}  
    cout<<dp[w];
}
2020/11/17 11:01
加载中...