萌新求调
查看原帖
萌新求调
649256
LuCat_qwq楼主2022/1/5 19:07
#include <bits/stdc++.h>
using namespace std;
int n,m,w,stp;
int p[10010],v[10010],np[10010],nv[10010],f[10010],father[10010];
int getfather(int x) {
	if(father[x]==x) return x;
	father[x]=getfather(father[x]);
	return father[x];
}
void merge(int x,int y) {
	int fx=getfather(x);
	int fy=getfather(y);
	if(fx!=fy) {
		v[fx]+=v[fy];
		p[fx]+=p[fy];
		father[fy]=fx;
	}
}
int main() {
	cin>>n>>m>>w;
	int c,d;
	for(int i=1; i<=n; i++) {
		cin>>c>>d;
		p[i]=c;
		v[i]=d;
		father[i]=i;
	}
	for(int i=1; i<=m; i++) {
		int x,y;cin>>x>>y;
		merge(x,y);
	}
	for(int i=1; i<=n; i++)
		if(father[i]==i)
			for(int i=1; i<=stp; i++)
				for(int j=w; j>=np[i]; j--)
					f[j]=max(f[j],f[j-np[i]]+nv[i]);
		cout<<f[w];
}
2022/1/5 19:07
加载中...