• <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>

            misschuer

            常用鏈接

            統計

            積分與排名

            百事通

            最新評論

            hdu 1011 Starship Troopers

            http://acm.hdu.edu.cn/showproblem.php?pid=1011

            #include <iostream>
            #include <vector>
            #include <queue>
            #define MAXN 111
            using namespace std;
            #define MAX(a, b) a>b?a:b

            int
            val[MAXN][ 2 ];
            int
            dp[MAXN][MAXN];
            int
            n , c;
            bool
            vist[MAXN];

            struct
            ver {

            int
            v;
            int
            next;
            };


            ver e[MAXN*2];
            int
            p[MAXN], aid;

            void
            add(int a, int b) {

            e[aid].next = p[ a ];
            e[aid].v = b;
            p[ a ] = aid ++;

            swap(a, b);

            e[aid].next = p[ a ];
            e[aid].v = b;
            p[ a ] = aid ++;
            }


            //dp[ i ][ k ] 表示以i為根節點用了k個人去消滅蟲的最大值
            //dp[ 1 ][ c ] 為結果
            //當trooper = 0 時, 即使不花費任何代價也拿不了, 和背包搞混了, 杯具

            void
            dfs (int x) {

            int
            i, j, k;
            int
            num = (val[ x ][ 0 ] + 19) / 20;
            for
            (i = num; i <= c; ++ i) {

            dp[ x ][ i ] = val[ x ][ 1 ];
            }


            vist[ x ] = true;

            for
            (i = p[ x ]; i != -1; i = e[ i ].next) {

            int
            y = e[ i ].v;

            if
            (vist[ y ]) continue;

            dfs (y);

            for
            (j = c; j >= num; -- j) {

            for
            (k = 1; j + k <= c; ++ k) {

            if
            (dp[ y ][ k ]) {

            dp[ x ][j + k] = MAX(dp[ x ][j + k], dp[ x ][ j ] + dp[ y ][ k ]);
            }
            }
            }
            }
            }


            int
            main() {

            int
            i, m;
            while
            (cin >> n >> c) {

            if
            (n == -1 && c == -1) break;

            memset(dp, 0, sizeof(dp));
            memset(vist, false, sizeof(vist));
            memset(p, -1, sizeof(p));
            aid = 0;

            for
            (i = 1; i <= n ; ++ i) {

            cin >> val[ i ][ 0 ] >> val[ i ][ 1 ];
            }


            m = n;
            while
            (-- m) {

            int
            a, b;
            cin >> a >> b;

            add(a, b);
            }


            if
            (c == 0) {

            cout << 0 << endl;
            continue
            ;
            }


            dfs (1);

            cout << dp[ 1 ][ c ] << endl;
            }

            return
            0;
            }

            posted on 2011-03-12 13:19 此最相思 閱讀(556) 評論(0)  編輯 收藏 引用

            久久综合九色综合精品| 国产成人久久激情91| 国产精品99久久久久久猫咪| 久久久99精品成人片中文字幕| 久久久久黑人强伦姧人妻| 久久久久国色AV免费观看| 亚洲成色www久久网站夜月| 国产精品丝袜久久久久久不卡| 日本亚洲色大成网站WWW久久| 日本一区精品久久久久影院| 久久九色综合九色99伊人| 亚洲国产精品成人久久| 国产精品亚洲美女久久久| 漂亮人妻被中出中文字幕久久| 精品久久久无码中文字幕天天| 91久久婷婷国产综合精品青草| 国产福利电影一区二区三区久久久久成人精品综合 | 99久久夜色精品国产网站| 狠狠人妻久久久久久综合| 亚洲欧美国产日韩综合久久| 精品久久国产一区二区三区香蕉| 久久毛片一区二区| 久久亚洲精品国产亚洲老地址| 国产V综合V亚洲欧美久久| 少妇内射兰兰久久| 久久久久国产视频电影| 2021少妇久久久久久久久久| 色老头网站久久网| 久久久久人妻精品一区三寸蜜桃 | 久久这里只精品国产99热| 欧美国产成人久久精品| 久久久人妻精品无码一区 | 91麻豆精品国产91久久久久久| 久久综合狠狠综合久久综合88| 一本一本久久A久久综合精品 | 久久精品视频网| 97久久精品无码一区二区| 久久精品国产2020| 久久久久免费看成人影片| 国产精品99久久久久久人| 无码国内精品久久人妻蜜桃|