• <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>
            付翔的專欄
            在鄙視中成長 記錄成長的點滴
            posts - 106,  comments - 32,  trackbacks - 0
             

            Constructing Roads

            Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
            Total Submission(s): 3780    Accepted Submission(s): 1298


            Problem Description
            There are N villages, which are numbered from 1 to N, and you should build some roads such that every two villages can connect to each other. We say two village A and B are connected, if and only if there is a road between A and B, or there exists a village C such that there is a road between A and C, and C and B are connected. 

            We know that there are already some roads between some villages and your job is the build some roads such that all the villages are connect and the length of all the roads built is minimum.
             

            Input
            The first line is an integer N (3 <= N <= 100), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 1000]) between village i and village j.

            Then there is an integer Q (0 <= Q <= N * (N + 1) / 2). Then come Q lines, each line contains two integers a and b (1 <= a < b <= N), which means the road between village a and village b has been built.

            Output
            You should output a line contains an integer, which is the length of all the roads to be built such that all the villages are connected, and this value is minimum.


            #include<iostream>
            #include
            <string.h>
            using namespace std;

            #define infinity 123456789
            #define max_vertexes 100 

            typedef 
            int Graph[max_vertexes][max_vertexes];

            Graph G;
            int total;
            int lowcost[max_vertexes],closeset[max_vertexes],used[max_vertexes];
            int father[max_vertexes];
            void prim(Graph G,int vcount)
            {
                
            int i,j,k;
                
            int min = infinity;
                
            for (i=0;i<vcount;i++)
                {
                    lowcost[i]
            =G[0][i];
                    closeset[i]
            =0
                    used[i]
            =0;
                    father[i]
            =-1
                }
                used[
            0]=1
                
                
            for (i=1;i<vcount;i++)
                {
                    j
            =0;
                    
                    
            while (used[j]) j++;
                    min 
            = lowcost[j];
                    
            for (k=0;k<vcount;k++)
                        
            if ((!used[k])&&(lowcost[k]<min)) 
                        {
                            min 
            =lowcost[k];
                            j
            =k;
                        }
                        father[j]
            =closeset[j]; 
                        used[j]
            =1;
                        total 
            += min;
                        
            for (k=0;k<vcount;k++)
                            
            if (!used[k]&&(G[j][k]<lowcost[k]))
                            { 
                                lowcost[k]
            =G[j][k];
                                closeset[k]
            =j; 
                            }
                }
            }

            int main()
            {
                
            int N,i,j,Q;
                
            int x,y;
                
            while(cin>>N)
                {
                    
                    total 
            = 0;
                    
            for(i =0; i< N;i++)
                    {
                        
            for(j = 0;j < N; j ++)
                            cin
            >>G[i][j];
                    }
                    cin
            >>Q;
                    
            for(i = 0; i < Q; i ++)
                    {
                        cin
            >>x>>y;
                        G[x
            -1][y-1= 0;
                        G[y
            -1][x-1= 0;
                    }
                    prim(G,N);
                    cout
            << total<<endl;
                }
                
            return 0;
            }


            posted on 2010-09-02 23:48 付翔 閱讀(293) 評論(0)  編輯 收藏 引用 所屬分類: ACM 圖論

            <2010年5月>
            2526272829301
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            CSDN - 我的blog地址

            博客

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            色8激情欧美成人久久综合电| 国内精品欧美久久精品| 久久久久久久久久久免费精品| 久久午夜福利无码1000合集| 99久久亚洲综合精品成人| 久久强奷乱码老熟女网站| 99蜜桃臀久久久欧美精品网站| 1000部精品久久久久久久久| 中文字幕亚洲综合久久2| 亚洲精品乱码久久久久久不卡| 亚洲精品乱码久久久久久不卡| 综合网日日天干夜夜久久| 韩国免费A级毛片久久| 久久人人爽人人爽AV片| 久久精品成人欧美大片| aaa级精品久久久国产片| 久久人与动人物a级毛片| 久久亚洲综合色一区二区三区| 中文字幕精品久久| 国产精品久久永久免费| 久久无码高潮喷水| 精品久久人人妻人人做精品| 久久久久无码精品国产| 久久久久久久波多野结衣高潮| 久久一区二区免费播放| 国产精品久久久久久久久| 欧美日韩成人精品久久久免费看 | 色综合久久88色综合天天 | 欧美午夜A∨大片久久| 久久精品亚洲日本波多野结衣| 久久久久久久波多野结衣高潮| 国产高潮国产高潮久久久91| 久久久久亚洲精品无码蜜桃| 久久久久亚洲av成人网人人软件| 日本免费一区二区久久人人澡| 色婷婷综合久久久久中文| 久久WWW免费人成一看片| 久久AV无码精品人妻糸列| 亚洲午夜久久久影院伊人| 久久99热只有频精品8| 久久久久夜夜夜精品国产|