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

            The Fourth Dimension Space

            枯葉北風(fēng)寒,忽然年以殘,念往昔,語默心酸。二十光陰無一物,韶光賤,寐難安; 不畏形影單,道途阻且慢,哪曲折,如渡飛湍。斬浪劈波酬壯志,同把酒,共言歡! -如夢令

            pku 3164 最小樹形圖(Zhu-Liu Algorithm)

            所謂的最小樹形圖,就是讓你在一個有向圖中找一個根和由根擴(kuò)展出來的一顆有向的生成樹,并且使這棵樹的權(quán)值最小。
            令人欣喜的是,這個算法是由中國人提出來的,這也是我正式學(xué)習(xí)的第一個中國人提出來的算法^_^

            最小樹形圖算法
            (Zhu-Liu Algorithm)

            1.       設(shè)最小樹形圖的總權(quán)值為cost,置cost0

            2.       除源點(diǎn)外,為其他所有節(jié)點(diǎn)Vi找一條權(quán)值最小的入邊,加入集合TT就是最短邊的集合。加邊的方法:遍歷所有點(diǎn)到Vi的邊中權(quán)值最小的加入集合T,記pre[Vi]為該邊的起點(diǎn),mincost[Vi]為該邊的權(quán)值。

            3.       檢查集合T中的邊是否存在有向環(huán),有則轉(zhuǎn)到步驟4,無則轉(zhuǎn)到步驟5。這里需要利用pre數(shù)組,枚舉檢查過的點(diǎn)作為搜索的起點(diǎn),類似dfs的操作判斷有向環(huán)。

            4.       將有向環(huán)縮成一個點(diǎn)。設(shè)環(huán)中有點(diǎn){Vk1,Vk2,…,Vki}i個點(diǎn),用Vk代替縮成的點(diǎn)。在壓縮后的圖中,更新所有不在環(huán)中的點(diǎn)VVk的距離:

            map[V][Vk] = min {map[V][Vkj]-mincost[Vki]} 1<=j<=i

            map[Vk][V] = min {map[Vkj][V]}           1<=j<=I

            5.       cost加上T中有向邊的權(quán)值總和就是最小樹形圖的權(quán)值總和。

            源代碼如下:(參考了網(wǎng)上的代碼)
            #include<iostream>
            #include
            <cstring>
            #include
            <cstdio>
            #include
            <cmath>
            using namespace std;

            #define INF 99999999
            #define min( a, b ) ( (a)< (b)?(a): (b) )

            struct point
            {

                
            double x;
                
            double y;
            }
            p[200];

            int pre[200];//記錄該節(jié)點(diǎn)的前驅(qū)
            double graph[200][200], ans;//圖數(shù)組和結(jié)果
            bool   visit[110], circle[110];//visit記錄該點(diǎn)有沒有被訪問過,circle記錄改點(diǎn)是不是在一個圈里
            int    n, m, root;//頂點(diǎn)數(shù)+邊數(shù)+根節(jié)點(diǎn)標(biāo)號

            void dfs( int t )//一個深度優(yōu)先搜索,搜索出一個最大的聯(lián)通空間
            {
                
            int i;
                visit[t]
            = true;
                
            for(i= 1; i<= n; ++i )
                
            {
                    
            if!visit[i] && graph[t][i]!= INF )
                        dfs( i );
                }

            }


            bool check()//這個函數(shù)用來檢查最小樹形圖是否存在,即如果存在,那么一遍dfs后,應(yīng)該可以遍歷到所有的節(jié)點(diǎn)
            {
                memset( visit, 
            falsesizeof(visit) );
                dfs( root );
                
                
            forint i= 1; i<= n; ++i )
                
            {
                    
            if!visit[i] ) 
                        
            return false;
                }

                
            return true;
            }


            double dist( int i, int j )
            {
                
            return sqrt( (p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y) );
            }


            int exist_circle()//判斷圖中是不是存在有向圈
            {
                
            int i;
                
            int j;
                root
            = 1; pre[root]= root;
                
            for(i= 1; i<= n; ++i )
                
            {
                    
            if!circle[i] && i!= root )
                    
            {
                        pre[i]
            = i; graph[i][i]= INF;
                        
                        
            for(j= 1; j<= n; ++j )
                        
            {
                            
            if!circle[j] && graph[j][i]< graph[pre[i]][i] )
                                pre[i]
            = j;
                        }

                    }

                }
            //這個for循環(huán)負(fù)責(zé)找出所有非根節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
                for( i= 1; i<= n; ++i )
                
            {
                    
            if( circle[i] ) 
                        
            continue;
                    memset( visit, 
            falsesizeof(visit) );
                    
            int j= i;
                    
            while!visit[j] ) 
                    

                        visit[j]
            = true
                        j
            = pre[j]; 
                    }

                    
            if( j== root )
                        
            continue;
                    
                    
            return j;
                }
            //找圈過程,最后返回值是圈中的一個點(diǎn)
                
                
            return -1;//如果沒有圈,返回-1
            }



            void  update( int t )//縮圈之后更新數(shù)據(jù)
            {
                
            int i;
                
            int j;
                ans
            += graph[pre[t]][t];
                
            for(i=pre[t]; i!= t; i= pre[i] )
                
            {
                    ans
            += graph[pre[i]][i];
                    circle[i]
            = true;
                }
            //首先把圈里的邊權(quán)全部加起來,并且留出t節(jié)點(diǎn),作為外部接口
                
                
            for(i= 1; i<= n; ++i )
                    
            if!circle[i] && graph[i][t]!= INF )
                        graph[i][t]
            -= graph[pre[t]][t];
                
            //上面這個for循環(huán)的作用是對t節(jié)點(diǎn)做更新操作,為什么要單獨(dú)做?你可以看看線面這個循環(huán)的跳出條件。
                for(j= pre[t]; j!= t; j= pre[j] )
                    
            forint i= 1; i<= n; ++i )
                    
            {
                        
            if( circle[i] ) 
                            
            continue;
                        
            if( graph[i][j]!= INF )
                        graph[i][t]
            = min( graph[i][t], graph[i][j]- graph[pre[j]][j] );
                        
            //////////////////////////////////////////////////////////////////////////
                        graph[t][i]= min( graph[j][i], graph[t][i] );
                    }

                
            //這個循環(huán)對圈中的其他頂點(diǎn)進(jìn)行更新
            }


            void solve()
            {
                
            int j;
                memset( circle, 
            falsesizeof(circle) );
                
            while( ( j= exist_circle() )!= -1 ) 
                    update( j );
                
                
            for( j= 1; j<= n; ++j )
                    
            if( j!= root && !circle[j] )
                        ans
            += graph[pre[j]][j];
                
                printf(
            "%.2lf\n", ans );
            }


            int main()
            {
                
            int i;
                
            while( scanf("%d%d",&n,&m)!= EOF )
                
            {
                    
            for(i= 0; i<= n; ++i )
                        
            forint j= 0; j<= n; ++j )
                            graph[i][j]
            = INF;
                    
                    
            for(i= 1; i<= n; ++i )
                        scanf(
            "%lf%lf",&p[i].x, &p[i].y );
                    
                    
            for(i= 0; i< m; ++i )
                    
            {
                        
            int a, b;
                        scanf(
            "%d%d",&a,&b);
                        graph[a][b]
            = dist( a, b );
                    }

                    
                    root
            = 1
                    ans
            = 0;
                    
            if!check() ) 
                        printf(
            "poor snoopy\n");
                    
            else  
                        solve();
                }

                
                
            return 0;
            }



            posted on 2009-10-29 19:38 abilitytao 閱讀(2176) 評論(2)  編輯 收藏 引用

            評論

            # re: pku 3164 最小樹形圖(Zhu-Liu Algorithm) 2009-10-30 11:58 淘寶網(wǎng)首頁

            學(xué)習(xí)!學(xué)習(xí)~~  回復(fù)  更多評論   

            # re: pku 3164 最小樹形圖(Zhu-Liu Algorithm) 2009-11-03 16:31 argmax

            這個算法應(yīng)該叫Chu-Liu-Edmond算法吧!  回復(fù)  更多評論   


            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            精品久久久久久无码中文野结衣 | 久久无码高潮喷水| 久久亚洲精品成人AV| 国产精品久久久久久久app| 国产亚州精品女人久久久久久| 99久久精品日本一区二区免费| 久久久久久国产精品美女| 久久人人爽人人爽人人片AV麻豆| 久久久久国产精品| 91精品国产综合久久婷婷| 日本久久久久亚洲中字幕| 亚洲精品无码久久久久久| 久久天天躁狠狠躁夜夜躁2014| 久久毛片一区二区| 久久婷婷五月综合成人D啪| 欧美成人免费观看久久| 狠狠色丁香婷婷久久综合| 久久99久国产麻精品66| 狠狠综合久久AV一区二区三区| 久久精品国产亚洲AV影院 | 伊人色综合久久天天网| 久久99精品国产麻豆不卡| 久久国产高清一区二区三区| 久久性精品| 日韩欧美亚洲综合久久| 午夜天堂精品久久久久| 99久久精品午夜一区二区| 一本一道久久精品综合| 久久久久无码精品| 2021国产精品午夜久久| 久久精品欧美日韩精品| 久久精品国内一区二区三区| 精品久久久久久国产三级| 亚洲伊人久久综合中文成人网| 中文字幕无码精品亚洲资源网久久| 乱亲女H秽乱长久久久| 国产成人久久久精品二区三区| 欧洲国产伦久久久久久久 | 国产精品视频久久久| 久久精品二区| 久久久www免费人成精品|