• <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)  編輯 收藏 引用

            欧美777精品久久久久网| 国内精品久久久久久久亚洲| 97精品伊人久久大香线蕉| 亚洲国产视频久久| 午夜精品久久久久久毛片| 国产精品9999久久久久| 久久精品亚洲乱码伦伦中文| 国产精品久久久久a影院| 国产99精品久久| 亚洲人成无码久久电影网站| 精品久久8x国产免费观看| 青春久久| 韩国三级中文字幕hd久久精品 | 色欲av伊人久久大香线蕉影院| 国内精品久久久久伊人av| 久久无码人妻精品一区二区三区| 人妻无码αv中文字幕久久琪琪布 人妻无码久久一区二区三区免费 人妻无码中文久久久久专区 | 久久精品国产99国产精偷 | 久久伊人亚洲AV无码网站| 久久国产精品77777| 久久青青国产| 亚洲国产精久久久久久久| 久久热这里只有精品在线观看| 国产成人综合久久久久久| 久久精品人成免费| 无码人妻久久一区二区三区 | 国内高清久久久久久| 久久国产免费直播| 日本精品久久久久中文字幕| 精品久久久久久亚洲精品| 亚洲va久久久噜噜噜久久天堂 | 色综合久久88色综合天天 | 国产精品99久久精品爆乳| 久久精品国产亚洲AV香蕉| 久久无码AV中文出轨人妻| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 久久久久99精品成人片三人毛片| 久久天天日天天操综合伊人av| 亚洲国产成人乱码精品女人久久久不卡| 久久久婷婷五月亚洲97号色| 欧美亚洲国产精品久久|