• <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>
            隨筆 - 26  文章 - 6  trackbacks - 0
            <2010年4月>
            28293031123
            45678910
            11121314151617
            18192021222324
            2526272829301
            2345678

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            朋友

            • cqh
            • 大學室友...

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            dp[s][i]:記錄s結點,要得到一棵j個節點的子樹去掉的最少邊數
            考慮其兒子k
              1)如果不去掉k子樹,則
             dp[s][i] = min(dp[s][j]+dp[k][i-j])  0 <= j <= i

              2)如果去掉k子樹,則
             dp[s][i] =  dp[s][i]+1
            總的為
             dp[s][i] = min (min(dp[s][j]+dp[k][i-j]) ,  dp[s][i]+1 )

            #include <iostream>
            #define MAX 152
            #define INF 0x3ffffff
            using namespace std;

            /*
            dp[s][i]:記錄s結點,要得到一棵j個節點的子樹去掉的最少邊數
            考慮其兒子k
              1)如果不去掉k子樹,則
                dp[s][i] = min(dp[s][j]+dp[k][i-j])  0 <= j <= i

              2)如果去掉k子樹,則
                dp[s][i] =  dp[s][i]+1
            總的為
                dp[s][i] = min (min(dp[s][j]+dp[k][i-j]) ,  dp[s][i]+1 )
            */


            int dp[MAX][MAX];
            int son[MAX], bla[MAX], root, n, p;
            //son[i]:記錄i結點的兒子,bla[i]:記錄i結點的兄弟
            bool hf[MAX];
            //hf[i]:i結點是否有父親

            void dfs(int s)
            {
                
            int i, j, k, temp;
                
            for(i = 0; i <= p; i++)
                    dp[s][i] 
            = INF;
                dp[s][
            1= 0;
                k 
            = son[s];
                
            while(k){
                    dfs(k);
                    
            for(i = p; i >= 0; i--){
                        temp 
            = dp[s][i]+1;
                        
            for(j = 0; j <= i; j++){
                            
            if(dp[k][i-j] + dp[s][j] < temp)
                                temp 
            = dp[k][i-j] + dp[s][j];
                        }

                        dp[s][i] 
            = temp;
                    }

                    k 
            = bla[k];
                }

            }


            int slove(int root)
            {
                dfs(root);
                
            int i, ans;
                ans 
            = dp[root][p];
                
            for(i = 1; i <= n; i++){
                    
            if(dp[i][p] < ans)
                        ans 
            = dp[i][p] + 1;
                }

                
            return ans;
            }


            int main()
            {
                
            //freopen("data.txt", "r", stdin);
                int i, s, t;
                
            while(cin >> n >> p){
                    memset(son, 
            0sizeof(son));
                    
            for(i = 1; i < n; i++){
                        cin 
            >> s >> t;
                        bla[t] 
            = son[s];
                        son[s] 
            = t;
                        hf[t] 
            = true;
                    }

                    
            for(i = 1; i <= n; i++){
                        
            if(!hf[i])
                            root 
            = i;
                    }

                    cout 
            << slove(root) << endl;
                }

                
            return 0;
            }
            posted on 2009-05-15 11:37 longshen 閱讀(2275) 評論(2)  編輯 收藏 引用 所屬分類: poj

            FeedBack:
            # re: poj 1947 Rebuilding Roads -- 樹形DP 2009-07-17 19:03 Winter Legend
            HoHo ~
            代碼很直觀啊 ~ 寫得不錯 ! 學習了~  回復  更多評論
              
            # re: poj 1947 Rebuilding Roads -- 樹形DP 2010-10-04 23:36 czy
            good~好代碼,膜拜  回復  更多評論
              
            久久青青草原综合伊人| 国产精品99久久久久久宅男| 久久亚洲精品国产亚洲老地址| 少妇久久久久久被弄到高潮| 精品久久久久香蕉网| 国产欧美久久一区二区| 久久97久久97精品免视看秋霞| 久久这里有精品| 国产精品99久久久久久猫咪| 日韩欧美亚洲综合久久| 精品久久人人妻人人做精品| 精品国产乱码久久久久软件| 99久久国产亚洲高清观看2024| 色诱久久av| 91秦先生久久久久久久| 久久精品国产99久久久| 亚洲精品久久久www| 国产一区二区精品久久凹凸| 欧美精品久久久久久久自慰| 香蕉aa三级久久毛片| 岛国搬运www久久| 久久综合久久综合九色| 精品国产VA久久久久久久冰| 亚洲人成电影网站久久| 久久久国产一区二区三区| 久久综合九色综合久99| 999久久久免费精品国产| 午夜人妻久久久久久久久| 波多野结衣AV无码久久一区| 久久综合成人网| 亚洲伊人久久综合影院| 久久人人爽人爽人人爽av| 欧美精品福利视频一区二区三区久久久精品| 国产亚洲欧美成人久久片| 久久99精品久久久久久| 久久精品免费一区二区三区| 久久亚洲欧美日本精品| 免费观看成人久久网免费观看| 国产精品日韩深夜福利久久| 久久国产精品免费一区| 久久久精品日本一区二区三区 |