题目描述
Bob喜欢玩电脑游戏,特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。
他要建立一个古城堡,城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵,使得这些士兵能了望到所有的路。
注意,某个士兵在一个结点上时,与该结点相连的所有边将都可以被了望到。
请你编一程序,给定一树,帮Bob计算出他需要放置最少的士兵.
输入输出格式
输入格式:
第一行 N,表示树中结点的数目。
第二行至第N+1行,每行描述每个结点信息,依次为:该结点标号i,k(后面有k条边与结点I相连)。
接下来k个数,分别是每条边的另一个结点标号r1,r2,...,rk。
对于一个n(0<n<=1500)个结点的树,结点标号在0到n-1之间,在输入数据中每条边只出现一次。
输出格式:
输出文件仅包含一个数,为所求的最少的士兵数目。
例如,对于如下图所示的树:
0
1 2 3
答案为1(只要一个士兵在结点1上)。
输入输出样例
输入样例#1: 复制
4
0 1 1
1 2 2 3
2 0
3 0
输出样例#1: 复制
1
*****求树的最大独立集,和没有上司的舞会特别像啊
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 int i,j,n,son[1505][1505],p,t[1505],f[1505][5],s,k,vis[1505]; 7 int dp(int x) 8 { 9 f[x][0] = 0; 10 f[x][1] = 1; 11 for(int i = 1;i <= t[x];i++) 12 { 13 int y = son[x][i]; 14 dp(y); 15 f[x][1] += min(f[y][1],f[y][0]); 16 f[x][0] += f[y][1]; 17 } 18 } 19 int main() 20 { 21 scanf("%d",&n); 22 for(i = 1;i <= n;i++) 23 { 24 scanf("%d %d",&s,&k); 25 t[s] = k; 26 for(j = 1;j <= k;j++) 27 { 28 scanf("%d",&son[s][j]); 29 vis[son[s][j]] = 1; 30 } 31 } 32 for(i = 0;i <= n - 1;i++) 33 { 34 if(vis[i] == 0) 35 { 36 p = i; 37 break; 38 } 39 } 40 dp(p); 41 printf("%d",min(f[p][1],f[p][0])); 42 return 0; 43 }