• <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>
            數(shù)據(jù)加載中……

            URAL 1018 A Binary Apple Tree

            A Binary Apple Tree


            Time Limit: 1.0 second
            Memory Limit: 16 MB
            Let's imagine how apple tree looks in binary computer world. You're right, it looks just like a binary tree, i.e. any biparous branch splits up to exactly two new branches. We will enumerate by natural numbers the root of binary apple tree, points of branching and the ends of twigs. This way we may distinguish different branches by their ending points. We will assume that root of tree always is numbered by 1 and all numbers used for enumerating are numbered in range from 1 to N, where N is the total number of all enumerated points. For instance in the picture below N is equal to 5. Here is an example of an enumerated tree with four branches:
            2   5
            \ /
            3 4
            \ /
            1
            As you may know it's not convenient to pick an apples from a tree when there are too much of branches. That's why some of them should be removed from a tree. But you are interested in removing branches in the way of minimal loss of apples. So your are given amounts of apples on a branches and amount of branches that should be preserved. Your task is to determine how many apples can remain on a tree after removing of excessive branches.

            Input

            First line of input contains two numbers: N and Q (1 ≤ QN; 1 < N ≤ 100). N denotes the number of enumerated points in a tree. Q denotes amount of branches that should be preserved. Next N−1 lines contains descriptions of branches. Each description consists of a three integer numbers divided by spaces. The first two of them define branch by it's ending points. The third number defines the number of apples on this branch. You may assume that no branch contains more than 30000 apples.

            Output

            Output should contain the only number — amount of apples that can be preserved. And don't forget to preserve tree's root ;-)

            Sample

            input output
            5 2
            1 3 1
            1 4 10
            2 3 20
            3 5 20
                                             21

            簡析:
                  這是一個簡單的樹形動態(tài)規(guī)劃問題,大概可以拿來當這類題目的入門訓練題.雖然這是URAL上的第一個樹形DP,但是我奇怪的是它的通過率并不很高.
                  對于原題目的圖形,用數(shù)組value[a][b]表示a,b點間蘋果的個數(shù),用nd[p].L,nd[p].R分別表示節(jié)點p的左右兒子.通過build_tree(1)獲得數(shù)組nd[],從而獲得整棵樹的信息.
            接著,用ans[p][i]表示以節(jié)點p為祖宗的子樹,保留的枝條不超過i條時所能保留的最多的蘋果,狀態(tài)轉(zhuǎn)移有一下幾種情況.
            在除去多余枝條的后的圖中,
            1.  p只與一個兒子相連:
                ans[p][i]=max(ans[left_son][i-1]+value[left_son][p],ans[right_son][i-1]+value[right_son][p]);
            2.  p與兩個兒子相連:
                for (int j=0;j<=i-2;++j)
                  ans[p][i]=max(ans[p][i],ans[left_son][j]+ans[right_son][i-j-2]+d); 
                這里,d=value[left_son][p]+value[right_son][p];

            算法在o(N*Q*Q)級別
             1 #include<iostream>
             2 using namespace std;
             3 const int MAXN=102;
             4 int n,q,value[MAXN][MAXN],ans[MAXN][MAXN];
             5 struct node
             6 {
             7   int l,r;
             8 }nd[MAXN];
             9 
            10 void build_tree(int p)
            11 {
            12   int flg=0;
            13   for (int i=1;i<=n;++i)
            14     if (value[p][i] && (!nd[i].l))
            15       {
            16     flg=1;
            17     if (nd[p].l==0) nd[p].l=i;
            18     else
            19       {nd[p].r=i; break;}
            20       }
            21   if (!flg) return;
            22   if (nd[p].l) build_tree(nd[p].l);
            23   if (nd[p].r) build_tree(nd[p].r);
            24 }
            25 
            26 void calc(int p)
            27 {
            28   if (!nd[p].l) return;
            29   int l=nd[p].l,r=nd[p].r;
            30   calc(l);
            31   calc(r);
            32   ans[p][1]=max(value[l][p],value[r][p]);
            33 
            34   int d=value[l][p]+value[r][p];
            35   for (int i=2;i<=q;++i)
            36   {  
            37     ans[p][i]=max(ans[l][i-1]+value[l][p],ans[r][i-1]+value[r][p]);
            38     for (int j=0;j<=i-2;++j)
            39       ans[p][i]=max(ans[p][i],ans[l][j]+ans[r][i-j-2]+d);
            40   }
            41 }
            42 
            43 
            44 int main()
            45 {
            46   //freopen("data.in","r",stdin);
            47   //freopen("data.out","w",stdout);
            48   cin >> n >> q;
            49   memset(value,0,sizeof(value));
            50   for (int i=1;i<n;++i)
            51     {
            52       int a,b,c;
            53       cin >> a >> b >> c;
            54       value[a][b]=c;
            55       value[b][a]=c;
            56     }
            57   memset(nd,0,sizeof(nd));
            58   build_tree(1);
            59   calc(1);
            60   cout << ans[1][q] << endl;
            61   return 0;
            62 }
            63 



            posted on 2009-07-19 23:02 Chen Jiecao 閱讀(490) 評論(0)  編輯 收藏 引用 所屬分類: URAL

            久久99这里只有精品国产| 精品久久久久中文字| 久久久久一级精品亚洲国产成人综合AV区| 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲 | 国内精品久久久久久久97牛牛| 国产精品久久久久影院色| 欧美激情精品久久久久久久| 一本色道久久88综合日韩精品 | 久久精品国产影库免费看| 无码国内精品久久综合88 | 久久99国产精品久久99| 久久天天躁狠狠躁夜夜不卡 | 欧美亚洲国产精品久久高清| 欧美激情精品久久久久| 国产精品久久波多野结衣| 久久毛片免费看一区二区三区| 亚洲国产另类久久久精品| 久久综合精品国产一区二区三区 | 久久久国产精华液| 亚洲精品乱码久久久久久不卡| av无码久久久久不卡免费网站| 国内精品久久久久影院老司| 色综合色天天久久婷婷基地| 亚洲AV成人无码久久精品老人| 婷婷国产天堂久久综合五月| 亚洲精品99久久久久中文字幕| 久久国产精品99精品国产987| 青青草原精品99久久精品66| 亚洲中文字幕无码久久精品1| 国产一区二区久久久| 久久久久久A亚洲欧洲AV冫| 久久亚洲色一区二区三区| …久久精品99久久香蕉国产| 久久亚洲精品成人av无码网站| 久久亚洲AV无码精品色午夜| 综合久久精品色| 久久久久久久久久久| 亚洲综合日韩久久成人AV| 精品伊人久久大线蕉色首页| 亚洲第一极品精品无码久久| 久久午夜羞羞影院免费观看|