骑上彩虹

题目描述

小 A 和他的大家庭外出度假，他们想要乘着彩虹欣赏周围的景色，但是这样最会有一些问题。

在他们家族中，如果一个人想要骑上彩虹，那么他喜欢的所有人和喜欢他的所有人都必须一同骑上彩虹。如果一个人没有喜欢的人，也没有人喜欢他，那么他也可以乘上彩虹。

你被请来解决这个难题，小 A 会提供给你家族所有成员的体重，以及每个人喜欢的人的列表，同样给出的还有彩虹能承受的总重量，你需要计算出在以上条件下彩虹所能承载的最多人数。

为了方便描述，所有的家庭成员都被标号，从 $1$ 到 $n$。

输入格式

从 rainbow.in 读入数据。

有多组数据，每组数据之间有一空行。

对于每一组数据，第一行两个整数 $n,c$，其中 $n$ 表示家庭成员的总人数，$c$ 表示彩虹的承载量。

第二行为 $n$ 个数为 $1$ 到 $n$ 个家庭成员的体重 $a_i$。

接下来 $n$ 行，每行第一个数 $k_i$ 表示第 $i$ 个人有多少喜欢的人，接下来 $k_i$ 个整数为他喜欢的人的编号。

当 $n=0$ 且 $c=0$ 时则表示数据结束。

输出格式

输出到 rainbow.out 中。

对于每一组数据，输出可以同时骑彩虹的最大人数。

样例

样例输入

5 200
50 50 50 50 50
1 2
1 3
0
1 5
1 4

3 200
100 100 100
1 2
1 3
1 1

0 0

样例输出

3
0

数据范围与提示

对于 $20\%$ 的数据，$1\le n\le8$；
对于 $100\%$ 的数据，$1\le n,c,a_i\le1000$，保证数据组数不超过 $3$。

---

WA code：

#include<iostream>
#include<string.h>
using namespace std;
int dp[1005],fa[1005],a[1005];
int gen(int x){
	return ((fa[x]==x)?x:fa[x]=gen(fa[x]));
}
int main(){
	freopen("rainbow.in","r",stdin);
	freopen("rainbow.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	int n,c;
	while(cin>>n>>c){
		if(n==0&&c==0)break;
		for(int i=1;i<=n;i++){
			fa[i]=i;
		}
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		for(int i=1;i<=n;i++){
			int x;
			cin>>x;
			for(int j=1;j<=x;j++){
				int y;
				cin>>y;
				int gi=gen(i),gy=gen(y);
				if(gi!=gy){
					fa[gi]=gy;
					a[gy]+=a[gi];
				}
			}
		}
		memset(dp,0,sizeof dp);
		for(int i=1;i<=n;i++){
			if(fa[i]==i){
				for(int j=c;j>=a[i];j--){
					dp[j]=max(dp[j],dp[j-a[i]]+1);
				}
			}
		}
		cout<<dp[c]<<'\n';
	}
	return 0;
}