题意：给定一棵树，选择最小的节点，使得每个没有被选中的节点至少和一个已选节点相邻
思路：简单的树形DP
#include#include #include #include #include using namespace std; const int MAXN = 1600; vector g[MAXN]; int dp[MAXN][2],vis[MAXN]; int n,num,x; void dfs(int r){ if (vis[r]) return; vis[r] = 1; dp[r][0] = 0; dp[r][1] = 1; if (g[r].size() == 0) return; for (int i = 0; i < g[r].size(); i++){ int j = g[r][i]; if (vis[j]) continue; dfs(j); dp[r][0] += dp[j][1]; dp[r][1] += min(dp[j][0],dp[j][1]); } } int main(){ while (scanf("%d",&n) != EOF){ for (int i = 0; i <= n; i++) g[i].clear(); for (int i = 0; i < n; i++){ scanf("%d:(%d)",&x,&num); for (int j = 0; j < num; j++){ int y; scanf("%d",&y); g[x].push_back(y); g[y].push_back(x); } } memset(vis,0,sizeof(vis)); dfs(0); printf("%d\n",min(dp[0][0],dp[0][1])); } return 0; }