记录编号	343500	评测结果	AAAAAAAAAA
题目名称	搭配购买	最终得分	100
用户昵称	O(1)	是否通过	通过
代码语言	C++	运行时间	0.758 s
提交时间	2016-11-09 12:58:18	内存使用	0.92 MiB

#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
int pre[100001],w[100001],v[100001],c[100001];
int find(int x)
{
	int r=x;
	while(r!=pre[r])
	   r=pre[r];
	
	int i=x,j;
	while(i!=j)
	{
		j=pre[i];
		pre[i]=r;
		i=j;
	}
	return r;
}
void mix(int x,int y)
{
	int fx=find(x),fy=find(y);
	if(fx!=fy)
	{
		w[fy]+=w[fx];
		v[fy]+=v[fx];
		w[fx]=0;
		v[fx]=0;
		pre[fx]=fy;
	}
}
int main()
{
	ofstream fout("buy.out");
	ifstream fin("buy.in");
	int n,m,ww,i,j,k;
	fin>>n>>m>>ww;
	for(i=1;i<=n;i++)
	{
		fin>>w[i]>>v[i];
		pre[i]=i;
	}
	for(i=1;i<=m;i++)
	{
		fin>>j>>k;
		mix(j,k);
	}
	for(i=1;i<=n;i++)
	{
		if(v[i]==0)
		  continue;
		for(j=ww;j>=w[i];j--)
		  c[j]=max(c[j],c[j-w[i]]+v[i]);
	}
	fout<<c[ww]<<endl;
}