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

            糯米

            TI DaVinci, gstreamer, ffmpeg
            隨筆 - 167, 文章 - 0, 評論 - 47, 引用 - 0
            數據加載中……

            POJ 1985 Cow Marathon 動態規劃/深搜

            思路:
            1985也可以用1986的程序改改就行了。
            但是覺得不用什么算法也是可以做出1985的。

            想了一下,發現:
            路徑的最大值一定存在于兩個葉子節點中。
            如果只有一個葉子,那整個樹就是一條直線了。

            由于我們只是考慮葉子節點。那么對于每一個非葉子節點,我們只需要找出它下面的所有節點中,離它最遠的兩個葉子就行了。
            這兩個葉子節點的距離也就有可能成為答案。
            對于每個點,我們只需要保存一個值,就是該點下面的所有節點中,距離它最遠的一個葉子節點,和它的距離。
            對于每個點,遍歷完它的孩子之后,就知道“離它最遠的兩個葉子的距離”了。

            注意:
            代碼里需要處理“一條直線連著幾個點”這種情況,將這樣的幾個點縮成一個點比較好。不做這個處理一定會爆棧。最后一個數據是一條直線。(陰險)

            這份代碼跑了141MS,還算可以,呵呵。應該比直接用lca要快。

            #include <stdio.h>

            #define MAX_N 40032

            struct edge_node {
                
            struct edge_node *next;
                
            int idx, len;
            }
            ;
            struct edge_node edges[MAX_N*2];

            struct tree_node {
                
            struct edge_node *edge;
                
            int visited;
            }
            ;
            struct tree_node tree[MAX_N];
            int max_val;

            __inline 
            void add_edge(int idx, int a, int b, int len)
            {
                
            struct edge_node *= &edges[idx];
                e
            ->idx = b;
                e
            ->len = len;
                e
            ->next = tree[a].edge;
                tree[a].edge 
            = e;
            }


            int dfs(int idx)
            {
                
            struct edge_node *e;
                
            int sum, cnt, arr[2], r;

                sum 
            = 0;
                
            while (1{
                    tree[idx].visited 
            = 1;
                    cnt 
            = 0;
                    
            for (e = tree[idx].edge; e; e = e->next)
                        cnt 
            += !tree[e->idx].visited;
                    
            if (!cnt)
                        
            return sum;
                    
            if (cnt > 1)
                        
            break;
                    
            for (e = tree[idx].edge; tree[e->idx].visited; e = e->next);
                    sum 
            += e->len;
                    idx 
            = e->idx;
                }


                arr[
            0= arr[1= 0;
                
            for (e = tree[idx].edge; e; e = e->next) {
                    
            if (tree[e->idx].visited)
                        
            continue;
                    r 
            = dfs(e->idx) + e->len;
                    
            if (r >= arr[1]) {
                        arr[
            0= arr[1];
                        arr[
            1= r;
                    }
             else if (r >= arr[0])
                        arr[
            0= r;
                }


                r 
            = arr[0+ arr[1];
                
            if (r > max_val)
                    max_val 
            = r;

                
            return arr[1+ sum;
            }


            int main()
            {
                
            int m, n, a, b, len, i;
                
            char str[16];

                freopen(
            "e:\\test\\in.txt""r", stdin);

                scanf(
            "%d%d"&n, &m);
                
            for (i = 0; i < m*2; i += 2{
                    scanf(
            "%d%d%d%s"&a, &b, &len, str);
                    add_edge(i, a, b, len);
                    add_edge(i 
            + 1, b, a, len);
                }


                
            for (i = 1; i <= n; i++{
                    
            if (tree[i].visited)
                        
            continue;
                    a 
            = dfs(i);
                    
            if (a > max_val)
                        max_val 
            = a;
                }

                printf(
            "%d\n", max_val);

                
            return 0;
            }



            posted on 2010-03-10 19:14 糯米 閱讀(656) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            久久综合亚洲鲁鲁五月天| 国产精品久久久久AV福利动漫| 国产欧美久久久精品| 亚洲欧美精品伊人久久| 国内精品久久久久影院网站| 久久国产精品波多野结衣AV| 一本一道久久a久久精品综合| 久久亚洲国产成人精品性色| 久久91亚洲人成电影网站| 国产免费久久精品丫丫| 久久精品国产亚洲AV久| 国产午夜免费高清久久影院| 久久亚洲国产成人影院网站| 亚洲色欲久久久综合网| 久久se精品一区二区影院| 精品国产乱码久久久久久呢| 国产精品99久久99久久久| 精品久久久久久久中文字幕 | 精品久久久久久无码免费| 无码任你躁久久久久久久| 亚洲国产精品狼友中文久久久| 亚洲人成网亚洲欧洲无码久久| 国产精品免费看久久久香蕉| 久久人人爽人人爽人人片AV东京热| 嫩草影院久久国产精品| 中文字幕人妻色偷偷久久| 久久综合综合久久狠狠狠97色88| 99久久做夜夜爱天天做精品| 激情五月综合综合久久69| 国产精品岛国久久久久| 无码人妻久久一区二区三区免费丨| A级毛片无码久久精品免费| 国内精品久久人妻互换| 亚洲国产欧美国产综合久久| 久久亚洲精品无码aⅴ大香| 国产精品欧美久久久久无广告 | 久久久久成人精品无码中文字幕| 久久久久久免费视频| 色99久久久久高潮综合影院| 久久国产精品无码网站| 久久精品国产亚洲5555|