记录编号	570955	评测结果	A
题目名称	[POJ 1463]战略游戏	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.069 s
提交时间	2022-04-27 20:28:46	内存使用	5.76 MiB

#include <bits/stdc++.h>
#define OPEN(_x) freopen(#_x".in", "r", stdin); freopen(#_x".out", "w", stdout)
#define rep(_x, _y, _z) for (int _x = (_y); _x <= (_z); ++ _x)
#define rep1(_x, _y, _z) for (int _x = (_y); _x < (_z); ++ _x)
#define fi first
#define se second

using i64 = long long;
using PII = std::pair<int, int>;

const int N = 1510;
int n;
int h[N], e[N], ne[N], idx;
int f[N][2];
bool st[N];

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u) {
	f[u][0] = 0;
	f[u][1] = 1;
	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i];
		dfs(j);
		f[u][0] += f[j][1];
		f[u][1] += std::min(f[j][0], f[j][1]);
	}
}

int main() {
	OPEN(strategic);
	while (~scanf("%d", &n)) {
		memset(h, -1, sizeof h);
		memset(st, 0, sizeof st);
		idx = 0;
		rep1(i, 0, n) {
			int id, cnt;
			scanf("%d:(%d)", &id, &cnt);
			while (cnt --) {
				int v;
				scanf("%d", &v);
				add(id, v);
				st[v] = true;
			}
		}
		int root = 0;
		while (st[root]) root ++;
		dfs(root);
		printf("%d\n", std::min(f[root][0], f[root][1]));
	}
	return 0;
}