本题翻译过来:在一棵书上每条边都必须有一个或多个士兵节点,求最少的士兵节点的个数。
那么对于每一个节点来说有选与不选两种情况:dp[i][0/1];
如果选的话儿子节点选与不选都行:dp[i][1] = 1 + (儿子节点累加和)min(dp[u][0], dp[u][1]);
那么对于每一个节点来说有选与不选两种情况:dp[i][0/1];
如果选的话儿子节点选与不选都行:dp[i][1] = 1 + (儿子节点累加和)min(dp[u][0], dp[u][1]);
如果不选的话儿子节点就必须要选才行:dp[i][0] = (儿子节点累加和)dp[u][1];
//本题翻译过来:在一棵书上每条边都必须有一个或多个士兵节点,求最少的士兵节点的个数。
//那么对于每一个节点来说有选与不选两种情况:dp[i][0/1];
//如果选的话儿子节点选与不选都行:dp[i][1] = 1 + (儿子节点累加和)min(dp[u][0], dp[u][1]);
//如果不选的话儿子节点就必须要选才行:dp[i][0] = (儿子节点累加和)dp[u][1];
#include <bits/stdc++.h>
using namespace std;
// #define int long longyi
const int maxn = 1500+10;
int n;
vector<int> v[maxn];
int dp[maxn][2];
void dfs(int i, int fa) {
int len = v[i].size();
dp[i][1] = 1;
for (int k=0;k<len;k++) {
int j = v[i][k];
if (j==fa) continue;
dfs(j, i);
dp[i][1] += min(dp[j][0], dp[j][1]);
dp[i][0] += dp[j][1];
}
}
signed main() {
int x, y, num;
while (scanf("%d", &n)!=EOF) {
// memset(dp, 0, sizeof(dp));
for (int i=0;i<n;i++) {
dp[i][1]=dp[i][0]=0;
v[i].clear();
}
for (int i=0;i<n;i++) {
scanf("%d:(%d)", &x, &num);
while (num--) {
scanf("%d", &y);
v[x].push_back(y);
v[y].push_back(x);
}
}
dfs(0, -1);
cout<<min(dp[0][1], dp[0][0])<<endl;
}
return 0;
}

京公网安备 11010502036488号