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

            博客

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久综合成人网| 久久精品国产91久久麻豆自制| 国产午夜精品久久久久九九| 精品久久久久久国产三级 | 亚洲国产日韩欧美久久| 亚洲精品乱码久久久久久不卡| 奇米影视7777久久精品人人爽| 97久久天天综合色天天综合色hd| 91精品国产91久久久久久青草| 久久久久亚洲国产| 色综合久久综精品| 久久亚洲精品人成综合网| 精品久久久久久无码免费| 久久精品国产清高在天天线| 久久久久久噜噜精品免费直播| 久久亚洲欧美国产精品 | 久久亚洲精精品中文字幕| 久久久久国色AV免费看图片| 久久综合精品国产二区无码| 亚洲精品乱码久久久久久蜜桃| 久久久91精品国产一区二区三区| 中文字幕无码免费久久| 中文字幕精品久久| 久久综合狠狠综合久久97色| 久久99国产精品久久久| 久久国产精品成人影院| 综合网日日天干夜夜久久| 四虎国产精品免费久久| 久久久久人妻精品一区三寸蜜桃| av国内精品久久久久影院| 久久久久人妻精品一区二区三区| 亚洲狠狠婷婷综合久久蜜芽| 香蕉久久AⅤ一区二区三区| 日韩AV毛片精品久久久| 久久综合伊人77777| 一级a性色生活片久久无少妇一级婬片免费放| 久久免费国产精品一区二区| 国产精品久久网| 色综合久久最新中文字幕| 久久香蕉国产线看观看乱码| 久久99国产精品99久久|