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

            oyjpArt ACM/ICPC算法程序設計空間

            // I am new in programming, welcome to my blog
            I am oyjpart(alpc12, 四城)
            posts - 224, comments - 694, trackbacks - 0, articles - 6

            中南賽A題 Accumulation Degree

            Posted on 2008-05-05 20:59 oyjpart 閱讀(3059) 評論(9)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽
            Accumulation Degree
            Time Limit: 5000MS
            Memory Limit: 65536K
            Total Submissions: 248
            Accepted: 30

            Description

            Trees are an important component of the natural landscape because of their prevention of erosion and the provision of a specific ather-sheltered ecosystem in and under their foliage. Trees have also been found to play an important role in producing oxygen and reducing carbon dioxide in the atmosphere, as well as moderating ground temperatures. They are also significant elements in landscaping and agriculture, both for their aesthetic appeal and their orchard crops (such as apples). Wood from trees is a common building material.

            Trees also play an intimate role in many of the world's mythologies. Many scholars are interested in finding peculiar properties about trees, such as the center of a tree, tree counting, tree coloring. A(x) is one of such properties.

            A(x) (accumulation degree of node x) is defined as follows:

            1. Each edge of the tree has an positive capacity.
            2. The nodes with degree of one in the tree are named terminals.
            3. The flow of each edge can't exceed its capacity.
            4. A(x) is the maximal flow that node x can flow to other terminal nodes.

            Since it may be hard to understand the definition, an example is showed below:


            A(1)=11+5+8=24
            Details: 1->2 11
              1->4->3 5
              1->4->5 8(since 1->4 has capacity of 13)
            A(2)=5+6=11
            Details: 2->1->4->3 5
              2->1->4->5 6
            A(3)=5
            Details: 3->4->5 5
            A(4)=11+5+10=26
            Details: 4->1->2 11
              4->3 5
              4->5 10
            A(5)=10
            Details: 5->4->1->2 10

            The accumulation degree of a tree is the maximal accumulation degree among its nodes. Here your task is to find the accumulation degree of the given trees.

            Input

            The first line of the input is an integer T which indicates the number of test cases. The first line of each test case is a positive integer n. Each of the following n - 1 lines contains three integers x, y, z separated by spaces, representing there is an edge between node x and node y, and the capacity of the edge is z. Nodes are numbered from 1 to n.
            All the elements are nonnegative integers no more than 200000. You may assume that the test data are all tree metrics.

            Output

            For each test case, output the result on a single line.
             

            Sample Input

            1
            5
            1 2 11
            1 4 13
            3 4 5
            4 5 10

            Sample Output

            26

            Source


            這道題的基本思想是樹形DP,如果不能理解的話請試圖把雙向邊看成兩個單向邊,再比劃比劃就出來了。
            當然不一定非要以邊做為DP的單元,也可以歸到邊上(如果你有那份心的話)。
            比賽的時候因為數據量大而Stack Overflow,一直想寫人工模擬棧,但因為沒寫過,在比賽中寫不出來。

            五一節虛心的跟alpc62學習了怎么寫人工模擬棧,核心思想就是將同一個DFS內的不同DFS做個標記,這樣在出棧的時候就可以判斷自己所處的位置,也就知道自己該采取什么行動了。
            比如
            void DFS(int x) {
                for(int i = 0; i < head[x].size(); ++i) {
                   DFS(head[x][i]);
                }
            }
            如果把(x, i)這個2元組壓入棧也就知道自己現在所處的地方了。
            如果有更多的內部DFS,同樣是加對應的標記。

            當然,BFS也是一種很好的選擇(應該說大多數隊伍會選擇BFS而不是人工模擬棧)

            //Accumulation Degree in BFS

            #include <vector>
            #include <algorithm>
            #include <iostream>
            using namespace std;

            #define Min(a, b) (a<b?a:b)
            #define Max(a, b) (a>b?a:b)

            struct Node
            {
                int x, i, pre;
                Node() {}
                Node(int xx, int ii, int pp) {x=xx, i = ii, pre=pp;}
            };

            struct Edge
            {
                int x, w, dp;
                Edge() {}
                Edge(int xx, int ww, int dd=0) { x=xx,w=ww,dp=dd;}
            };

            const int N = 200010;
            vector<Edge> e[N];
            bool chk[N];
            int n, flow[N];

            void solve() {
                int i, j, k;
                vector<Node> Q;

                fill(chk, chk + n, 0);
                fill(flow, flow + n, 0);

                for(i = 0; i < n && e[i].size()!=1; ++i);
                int st = 0, end = 0;
                chk[i] = 1;
                for(j = 0; j < e[i].size(); ++j) {
                    Q.push_back(Node(i, j, -1));
                    end++;
                    chk[e[i][j].x] = 1;
                }
                while(st < end) {
                    int x = e[Q[st].x][Q[st].i].x, pre = Q[st].pre;
                    for(i = 0; i < e[x].size(); ++i) {
                        if(!chk[e[x][i].x]) {
                            Q.push_back(Node(x, i, st));
                            end++;
                            chk[e[x][i].x] = 1;
                        }
                    }
                    ++st;
                }
                for(i = end-1; i >= 0; --i) {
                    int x = Q[i].x, pre = Q[i].pre, idx = Q[i].i;
                    if(e[e[x][idx].x].size() == 1) e[x][idx].dp = e[x][idx].w;
                    else e[x][idx].dp = Min(e[x][idx].dp, e[x][idx].w);
                    if(pre == -1) continue;
                    int prex = Q[pre].x, preidx = Q[pre].i;
                    e[prex][preidx].dp += e[x][idx].dp;
                }


                for(i = 0; i < e[Q[0].x].size(); ++i) {
                    flow[Q[0].x] += e[Q[0].x][i].dp;
                }
                for(i = 0; i < end; ++i) {
                    int x = Q[i].x, pre = Q[i].pre, idx = Q[i].i;
                    int y = e[x][idx].x, xx;
                    for(xx = 0; xx < e[y].size() && e[y][xx].x != x; ++xx);
                    if(pre == -1) {
                        e[y][xx].dp = e[y][xx].w;
                    }
                    else {
                        e[y][xx].dp = Min(e[y][xx].dp, e[y][xx].w);
                    }
                    for(j = 0; j < e[y].size(); ++j) {
                        flow[y] += e[y][j].dp;
                    }
                    for(j = 0; j < e[y].size(); ++j) {
                        int yy = e[y][j].x;
                        if(yy == x) continue;
                        for(k = 0; k < e[yy].size() && e[yy][k].x != y; ++k);
                        e[yy][k].dp = flow[y] - e[y][j].dp;
                    }
                }

                int max = 0;
                for(i = 0; i < n; ++i)
                    max = Max(max, flow[i]);
                printf("%d\n", max);
            }

            int main() {
                int ntc;
                int i;
                int x, y, w;
                scanf("%d", &ntc);
                while(ntc--) {
                    scanf("%d", &n);
                    for(i = 0; i < n; ++i) e[i].clear();
                    for(i = 0; i < n-1; ++i) {
                        scanf("%d %d %d", &x, &y, &w);
                        --x; --y;
                        e[x].push_back(Edge(y, w));
                        e[y].push_back(Edge(x, w));
                    }
                    solve();
                }
                return 0;
            }


            Feedback

            # re: 中南賽A題 Accumulation Degree  回復  更多評論   

            2008-05-06 14:41 by wlzb
            不錯呀,上原創精華了

            # re: 中南賽A題 Accumulation Degree  回復  更多評論   

            2008-05-06 18:00 by oyjpart
            哦?

            # re: 中南賽A題 Accumulation Degree  回復  更多評論   

            2008-05-12 21:15 by alpc55
            太強了,你竟然模擬棧……

            # re: 中南賽A題 Accumulation Degree  回復  更多評論   

            2008-05-13 22:52 by ecnu_zp
            哦~~
            學習學習·~

            公網能進你們的oj系統嗎??

            # re: 中南賽A題 Accumulation Degree  回復  更多評論   

            2008-05-13 22:52 by ecnu_zp
            哦~~
            學習學習·~

            公網能進你們的oj系統嗎??
            教育網

            # re: 中南賽A題 Accumulation Degree  回復  更多評論   

            2008-05-13 23:50 by oyjpart
            我們是軍網 外網應該不能訪問

            # re: 中南賽A題 Accumulation Degree  回復  更多評論   

            2008-05-14 17:15 by ecnu_zp
            我還是不太明白啊~
            我想的dp是N^2A的,因為要對所有點執行一次~~
            我弱,能不能教我一下啊。

            ecnu_zp@yahoo.cn
            QQ:345717212
            MSN: arena_zp@live.cn

            ^_^

            # re: 中南賽A題 Accumulation Degree  回復  更多評論   

            2008-05-14 20:08 by oyjpart
            每條邊拆成2條邊 。 然后對每條邊設一個DP值。
            比如邊A->B. B連接的其他點的集合叫做S(S中去掉A)
            dp[A->B] = Min(Capacity[A->B], 加合(dp[B->Ci]));
            可以通過2次DFS來求出這些DP值。第一次求出一個方向的邊的DP值,再一次求出反向。
            試著畫個圖來理解吧:)

            # re: 中南賽A題 Accumulation Degree  回復  更多評論   

            2008-07-26 06:06 by lengbufang
            看看!!
            亚洲欧美精品伊人久久| 久久99这里只有精品国产| 亚洲精品无码专区久久同性男| 久久精品无码免费不卡| 人人狠狠综合久久亚洲高清| 色综合久久夜色精品国产| 午夜精品久久久久久久久| 青青热久久综合网伊人| 久久精品国产清自在天天线| 亚洲国产成人久久综合碰碰动漫3d| 色综合久久中文色婷婷| 久久人人爽人人爽人人爽| 国产亚洲美女精品久久久久狼| 伊人久久大香线蕉AV一区二区| 色欲久久久天天天综合网精品| 国产香蕉97碰碰久久人人| 久久被窝电影亚洲爽爽爽| 2021最新久久久视精品爱| 91精品国产色综久久 | 久久精品99久久香蕉国产色戒| 国内精品久久久久久麻豆| 久久精品中文字幕一区| 色偷偷91久久综合噜噜噜噜| 久久99国产综合精品| 久久精品无码午夜福利理论片| 久久99久久无码毛片一区二区| 国产综合久久久久| 欧美日韩精品久久免费| 亚洲日韩欧美一区久久久久我| 久久久久四虎国产精品| 国产精品99精品久久免费| 麻豆一区二区99久久久久| 成人久久综合网| 久久99精品国产麻豆蜜芽| 色综合久久88色综合天天| 国产精品久久久久久久久| AV色综合久久天堂AV色综合在| 无码人妻久久一区二区三区免费丨 | 人妻中文久久久久| 中文字幕精品无码久久久久久3D日动漫| 国产日韩久久久精品影院首页|