分享

更多

   

小游戏分分彩源码下载

2018-03-15  彩票源码...

问题描述

小李很喜欢玩计算机游戏,特别是战略游戏分分彩源码下载(hxforum.com)企鹅 2952777280,但是有时他不能尽快找到解所以常常感到很沮丧。现在面临如下问题:他必须在一个中世纪的城堡里设防,城堡里的道路形成一棵无向树。要在结点上安排最少的士兵使得他们可以看到所有边。你能帮助他吗?

你的任务是给出士兵的最少数目。

输入格式

输入包含多组数据。每组数据表示一棵树,在每组数据中:

第一行是结点的数目。

接下来的几行,每行按如下格式描述一个结点:

结点标识符 : ( 道路的数目 ) 结点标识符1  结点标识符2  ……  结点标识符道路的数目

或者

结点标识符 : (0)

对于 n (0<n<=1500) 个结点,结点标识符是一个从 0 到 n - 1 的整数。每条边在测试用例中只出现一次。

输出格式

对于每组数据,各给出一个整数表示士兵的最少数目.

测试输入

4
0:(1) 1
1:(2) 2 3
2:(0)
3:(0)
5
3:(3) 1 4 2
1:(1) 0
2:(0)
0:(0)
4:(0)

测试输出

1
2

源代码

[objc] view plain copy
  1. #include <stdio.h>      
  2. #include <string.h>      
  3. #define min(x,y) ((x>y)?y:x)      
  4. #define N 1504       
  5. int dp[N][2], father[N], v[N], n;      
  6. int main()      
  7. {      
  8.     int i, j, k, t1, t2, root=0;      
  9.     void DFS(int root);      
  10.     while(scanf("%d",&n)!=EOF){      
  11.         memset(dp,0,sizeof(dp));      
  12.         memset(father,0,sizeof(father));      
  13.         memset(v,0,sizeof(v));      
  14.         for(i=0;i<n;i++){      
  15.             scanf("%d:(%d)",&t1,&t2);      
  16.             if(i==0) root=t1;      
  17.             for(j=0;j<t2;j++){      
  18.                 scanf("%d",&k);      
  19.                 father[k]=t1;      
  20.             }             
  21.         }      
  22.         DFS(root);      
  23.         printf("%d\n",min(dp[root][0],dp[root][1]));      
  24.     }      
  25.     return 0;      
  26. }      
  27.       
  28. void DFS(int root)      
  29. {      
  30.     v[root]=1;      
  31.     for(int i=0;i<n;i++){      
  32.         if(!v[i] && father[i]==root){      
  33.             DFS(i);      
  34.             dp[root][1]=dp[root][1]+dp[i][0];      
  35.             dp[root][0]=dp[root][0]+min(dp[i][0],dp[i][1]);      
  36.         }      
  37.     }      
  38.     dp[root][0]++;      
  39. }    

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。如发现有害或侵权内容,请点击这里 或 拨打24小时举报电话:4000070609 与我们联系。

    猜你喜欢

    0条评论

    发表

    类似文章 更多
    喜欢该文的人也喜欢 更多