本题翻译过来:在一棵书上每条边都必须有一个或多个士兵节点,求最少的士兵节点的个数。
那么对于每一个节点来说有选与不选两种情况: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; }