并查集+背包【CF741B】 Arpa's weak amphitheater and Mehrdad's valuable Hoses

Descirption

有n个人，每个人都有颜值bi与体重wi。剧场的容量为W。有m条关系，xi与yi表示xi和yi是好朋友，在一个小组。每个小组要么全部参加舞会，要么参加人数不能超过1人。问保证总重量不超过W，剧场中的颜值最大能到多少？

Input

第一行，三个整数n,m,w

第二行，n个整数w1,w2,...,wn

第三行，n个整数b1,b2,...,bn

接下来m行，每行表示一个关系，第i行有两个整数xi和yi。

每一组朋友关系都是不同的。

Output

一行，表示最大的魅力值总和。

不错的一个题。

考察：并查集+分组背包。

我们先并查集将在一组的人处理出来.

顺便处理一下每个组的编号与组中每个人是谁.

\(belong[x]\)则代表\(x\)组的编号。

我们用\(ins[i][j]\)代表第\(i\)组的第\(j\)个元素是谁。

然后每一个小组可以全部去,可以去一个,可以不去。

考虑问题转化,我们将这一个小组看成一个物品，直接把其价值及体积加入到当前组即可。

处理完之后,跑分组背包即可。

需要注意的一点是:如果某一组只有一个元素,我们不能再将其看为一个物品重新加入(克隆？)

代码

#include<cstdio>

#include<iostream>

#include<algorithm>

#define R register

using namespace std;

const int gz=1008;

inline void in(int &x)

{

	int f=1;x=0;char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

int n,m,w,wi[gz],f[gz],b[gz],dp[gz];

int find(R int x){return f[x]==x?x:f[x]=find(f[x]);}

int belong[gz],cnt;

int ins[gz][gz],W[gz],B[gz];

int main()

{

	in(n),in(m),in(w);

	for(R int i=1;i<=n;i++)in(wi[i]);

	for(R int i=1;i<=n;i++)in(b[i]);

	for(R int i=1;i<=n;i++)f[i]=i;

	for(R int i=1,x,y;i<=m;i++)

	{

		in(x),in(y);

		R int fa=find(x);

		R int fb=find(y);

		if(fa==fb)continue;

		f[fa]=fb;

	}

	for(R int i=1;i<=n;i++)

	{

		R int x=find(i);

		if(!belong[x])belong[x]=++cnt;

		ins[belong[x]][++ins[belong[x]][0]]=i;

		W[belong[x]]+=wi[i];

		B[belong[x]]+=b[i];

	}

	for(R int i=1;i<=cnt;i++)

	{

		if(ins[i][0]!=1)

		{

			ins[i][++ins[i][0]]=n+1;

			wi[n+1]=W[i];

			b[n+1]=B[i];

		}

	for(R int j=w;j>=0;j--)

		for(R int k=1;k<=ins[i][0];k++)

			if(j>=wi[ins[i][k]])

				dp[j]=max(dp[j],dp[j-wi[ins[i][k]]]+b[ins[i][k]]);

	}

	printf("%d",dp[w]);

}

巴特西

并查集+背包【CF741B】 Arpa's weak amphitheater and Mehrdad's valuable Hoses

Descirption

Input

Output

最新文章

热门文章

巴特西

并查集+背包 【CF741B】 Arpa's weak amphitheater and Mehrdad's valuable Hoses

Descirption

Input

Output

最新文章

热门文章

并查集+背包【CF741B】 Arpa's weak amphitheater and Mehrdad's valuable Hoses