九敏,RE4个点
查看原帖
九敏,RE4个点
530664
_Faith_楼主2022/8/11 17:30
#include<bits/stdc++.h>
using namespace std;
int ver[2010], hd[1010], idx, nxt[2020], dp[101][2];
int n;
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
inline void add(int x, int y) {
	ver[++idx] = y;
	nxt[idx] = hd[x];
	hd[x] = idx;
}
inline void dfs(int x, int y) {
	dp[x][1] = 1;
	dp[x][0] = 0;
	for (int i = hd[x]; i; i = nxt[i]) {
		if (ver[i] == y)
			continue;
		dfs(ver[i], x);
		dp[x][0] += dp[ver[i]][1];
		dp[x][1] += min(dp[ver[i]][1], dp[ver[i]][0]);
	}
}
int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		int x = read() + 1;
		int	k = read();
		for (int j = 1; j <= k; j++) {
			int	y = read() + 1;
			add(x, y);
			add(y, x);
		}
	}
	dfs(1, 0);
	cout << min(dp[1][0], dp[1][1]);
	return 0;
}
2022/8/11 17:30
加载中...