Never or now.
本文从WordPress迁移而来, 查看全部WordPress迁移文章
树dp
最小支配集问题啊…..放置最少的点覆盖所有的点。当点数为1输出1
12345678910111213141516171819202122232425262728293031323334353637383940414243
#include <iostream>#include <cstdio>#include <cstring>#include <vector>using namespace std;#define N 1010#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))#define pb push_backint n;vector<int>e[N];int dp[N][2];void dfs(int u,int fa){ dp[u][0] = dp[u][1] = 0; for(int i = 0; i < e[u].size(); i++){ int v = e[u][i]; if(v == fa) continue; dfs(v,u); dp[u][0] += dp[v][1]; dp[u][1] += min(dp[v][0],dp[v][1]); } dp[u][1]++;}int main(){ while(scanf("%d",&n)!=EOF && n){ for(int i = 0; i <= n; i++) e[i].clear(); for(int u = 1; u <= n; u++){ int k,v; scanf("%d",&k); while(k--){ scanf("%d",&v); e[u].pb(v); } } if(n == 1) { puts("1"); continue; } dfs(1,-1); printf("%d\n",min(dp[1][0],dp[1][1])); } return 0;}