随笔-65  评论-6  文章-0  trackbacks-0
 1 /*
 2 Author:    Leo.W
 3 Descriptipn:  给定一个树形的地图,用最少的树节点使得能够控制【即所有结点都能一个被占据的结点相连】全树。  
 4 How to Do:    dp[i][0]=sum{dp[son[i][j]][1]};
 5             dp[i][1]=sum{min(dp[son[i][j]][0],dp[son[i][j]][1])};
 6             建立结构体,对输入的信息,记录子树的个数及序号,初始是根节点
 7   */
 8 #include <iostream>
 9 using namespace std;
10 #define MAXSIZE 1501
11 int dp[MAXSIZE][2];//对于每一个结点的选择,放或不放,两种
12 struct node{
13     int num[MAXSIZE];
14     int lenth;
15     bool isAnc;
16 };
17 node nd[MAXSIZE];
18 inline int mins(int a,int b){
19     return a<b?a:b;
20 }
21 int dfs(int no,int alter){//序号及二选一的选择
22     if(dp[no][alter]!=INT_MIN)
23         return dp[no][alter];
24     int i,temp=nd[no].lenth;
25     int sum=0;
26     sum+=alter;
27     for(i=0;i<temp;i++){
28         int son=nd[no].num[i];
29         if(alter)
30             sum+=mins(dfs(son,0),dfs(son,1));
31         else
32             sum+=dfs(son,1);
33     }
34     return dp[no][alter]=sum;
35 }
36 int main(){
37     //freopen("in.txt","r",stdin);
38     int n;
39     while(scanf("%d",&n)!=EOF){
40         int i,j;
41         for(i=0;i<n;i++){
42             dp[i][0]=dp[i][1]=INT_MIN;
43             nd[i].isAnc=true;
44         }
45         for(i=0;i<n;i++){
46             int nodeNo,nodeNum;
47             scanf("%d:(%d)",&nodeNo,&nodeNum);
48             nd[nodeNo].lenth=nodeNum;
49             for(j=0;j<nodeNum;j++){
50                 int temp;
51                 scanf("%d",&temp);
52                 nd[nodeNo].num[j]=temp;
53                 nd[temp].isAnc=false;
54             }
55         }
56         for(i=0;i<n;i++)
57             if(nd[i].isAnc)
58                 break;
59         int ans=mins(dfs(i,0),dfs(i,1));
60         printf("%d\n",ans);
61     }
62     return 0;
63 }
posted on 2012-03-04 10:29 Leo.W 阅读(281) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理