第34~38题题目

（匠人的自我修养）一个匠人决定要学习n个新技术。要想成功学习一个新技术，他不仅要拥

有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验

值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经

验值，请问他最多能学会多少个新技术。

输入第一行有两个数，分别为新技术个数n(l <= n <= 103),以及己有经验值（≤107）。

接下来n行。第i行的两个正整数，分别表示学习第i个技术所需的最低经验值（≤107），以

及学会第i个技术后可获得的经验值（<=107)

接下来n行。第i行的第一个数mi（0 ≤ mi < n），表示第i个技术的相关技术数量。紧跟着

m个两两不同的数，表示第i个技术的相关技术编号。

输出最多能学会的新技术个数。

下面的程序以O(n2)的时间复杂度完成这个问题，试补全程序。

#include<iostream>
using namespace std;
const int maxn = 1001;
4
int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int threshold[maxn], bonus[maxn];
int points;
bool find() {
	int target = -1;
	for (int i = 1; i <= n; ++i)
		if(① && ②) {
			target = i;
			break
			;
		}
	if(target == -1)
		return false;
	unlock[target] = -1;
	③
	for (int i = 0; i < cnt[target]; ++i)
		④
		return true;
}

int main() {
	scanf("%d%d", &n, &points);
	for (int i = 1; i <= n; ++i) {
		cnt[i] = 0;
		scanf("%d%d", &threshold[i], &bonus[i]);
	}
	for (int i = 1; i <= n; ++i) {
		int m;
		scanf("%d", &m);
		⑤
		for (int j = 0; j < m; ++j) {
			int fa;
			scanf("%d", &fa);
			child[fa][cnt[fa]] = i;
			++cnt[fa];
		}
	}

	int ans = 0;
	while(find())
		++ans;

	printf("%d\n", ans);
	return 0;
}

①处应填（）