• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆-65  評(píng)論-6  文章-0  trackbacks-0
             1 /*
             2 Author:    Leo.W
             3 Descriptipn:  給定一個(gè)樹(shù)形的地圖,用最少的樹(shù)節(jié)點(diǎn)使得能夠控制【即所有結(jié)點(diǎn)都能一個(gè)被占據(jù)的結(jié)點(diǎn)相連】全樹(shù)。  
             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             建立結(jié)構(gòu)體,對(duì)輸入的信息,記錄子樹(shù)的個(gè)數(shù)及序號(hào),初始是根節(jié)點(diǎn)
             7   */
             8 #include <iostream>
             9 using namespace std;
            10 #define MAXSIZE 1501
            11 int dp[MAXSIZE][2];//對(duì)于每一個(gè)結(jié)點(diǎn)的選擇,放或不放,兩種
            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){//序號(hào)及二選一的選擇
            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 閱讀(293) 評(píng)論(0)  編輯 收藏 引用

            只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            久久久久亚洲av无码专区| 久久国产精品免费一区| 狠狠综合久久AV一区二区三区| 亚洲欧美一级久久精品| 精品综合久久久久久888蜜芽| 国产高清美女一级a毛片久久w| 亚洲精品tv久久久久| 国产精品久久久久jk制服| 久久99精品久久久久久齐齐| 久久婷婷色综合一区二区| 亚洲国产精品久久| 97精品依人久久久大香线蕉97| 国产成人久久精品一区二区三区| 久久国产精品免费一区| 久久精品无码午夜福利理论片| 久久综合伊人77777| 久久99精品久久久久久久久久| 日韩欧美亚洲综合久久影院Ds| 久久国产精品77777| 久久人人爽人人澡人人高潮AV| 国产成人久久精品一区二区三区| 理论片午午伦夜理片久久| 国内精品伊人久久久久AV影院| 色综合久久夜色精品国产| 伊人久久精品无码av一区| 国产亚洲成人久久| 久久久久人妻精品一区二区三区| 久久久久亚洲精品天堂久久久久久| 99国产精品久久久久久久成人热| 亚洲第一极品精品无码久久 | 漂亮人妻被黑人久久精品| 亚洲欧美成人久久综合中文网| 99热热久久这里只有精品68| 久久久久久无码Av成人影院| 国产精品久久久久久五月尺| 婷婷久久综合九色综合绿巨人| 久久久久亚洲AV综合波多野结衣| 久久久免费观成人影院| 亚洲伊人久久综合中文成人网| 欧美久久综合九色综合| 久久婷婷午色综合夜啪|