网站主题下载,微信支付 网站开发,985短网址生成,全球4a广告公司排名题目描述 Bob喜欢玩电脑游戏#xff0c;特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。 他要建立一个古城堡#xff0c;城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵#xff0c;使得这些士兵能了望到所有的路。 注意#xff0…题目描述 Bob喜欢玩电脑游戏特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。 他要建立一个古城堡城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵使得这些士兵能了望到所有的路。 注意某个士兵在一个结点上时与该结点相连的所有边将都可以被了望到。 请你编一程序给定一树帮Bob计算出他需要放置最少的士兵. 输入格式 第一行 N表示树中结点的数目。 第二行至第N1行每行描述每个结点信息依次为该结点标号ik(后面有k条边与结点I相连)。 接下来k个数分别是每条边的另一个结点标号r1r2...rk。 对于一个n(0n1500)个结点的树结点标号在0到n-1之间在输入数据中每条边只出现一次。 输出格式 输出文件仅包含一个数为所求的最少的士兵数目。 例如对于如下图所示的树 0
1
2 3答案为1只要一个士兵在结点1上。 输入输出样例 输入 #14
0 1 1
1 2 2 3
2 0
3 0输出 #1 1 分析 树的最大独立集模板题。。。F[i][0]表示当前位置不放的最小值F[i][1]表示当前位置放的最小值。 CODE 1 #includecmath2 #includecstdio3 #includecstring4 #includeiostream5 #includealgorithm6 using namespace std;7 const int M1505;8 struct node{9 int num;
10 int child[M];
11 }k[M];
12 int f[M][2],a[M],n,root;
13 void dp(int x){
14 f[x][1]1;
15 f[x][0]0;
16 if (k[x].num0) return ;
17 for (int i1;ik[x].num;i){
18 dp(k[x].child[i]);
19 f[x][0]f[k[x].child[i]][1];
20 f[x][1]min(f[k[x].child[i]][0],f[k[x].child[i]][1]);
21 }
22 }
23 int main() {
24 cinn;
25 for (int i1;in;i){
26 int x,y;
27 cinx;
28 cink[x].num;
29 for (int j1;jk[x].num;j){
30 ciny;
31 k[x].child[j]y;
32 a[y]1;
33 }
34 }
35 while (a[root]) root;
36 dp(root);
37 coutmin(f[root][0],f[root][1])endl;
38 //system(pause);
39 return 0;
40 } 转载于:https://www.cnblogs.com/kanchuang/p/11243503.html
