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

            ACM___________________________

            ______________白白の屋
            posts - 182, comments - 102, trackbacks - 0, articles - 0
            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(24)

            隨筆分類(332)

            隨筆檔案(182)

            FRIENDS

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋    

             

            題目地址:

            http://poj.org/problem?id=1258

            題目描述:

            Agri-Net
            Time Limit: 1000MSMemory Limit: 10000K
            Total Submissions: 16557Accepted: 6745

            Description

            Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course. 
            Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms. 
            Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm. 
            The distance between any two farms will not exceed 100,000. 

            Input

            The input includes several cases. For each case, the first line contains the number of farms, N (3 <= N <= 100). The following lines contain the N x N conectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem.

            Output

            For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.

            Sample Input

            4
            0 4 9 21
            4 0 8 17
            9 8 0 16
            21 17 16 0
            

            Sample Output

            28

            題目分析 :
             	MST 水題, 用KRUSKARL 或 PRIM 輕松能過.
            代碼如下 :
            /*
            Mail to   : miyubai@gamil.com
            MyBlog    : http://baiyun.me
            Link      : http://www.cnblogs.com/MiYu  || http://www.shnenglu.com/MiYu
            Author By : MiYu
            Test      : 1
            Complier  : g++ mingw32-3.4.2
            Program   : Agri-Net
            Doc Name  : PKU_1258
            */
            //#pragma warning( disable:4789 )
            #include <iostream>
            #include <fstream>
            #include <sstream>
            #include <algorithm>
            #include <string>
            #include <set>
            #include <map>
            #include <utility>
            #include <queue>
            #include <stack>
            #include <list>
            #include <vector>
            #include <cstdio>
            #include <cstdlib>
            #include <cstring>
            #include <cmath>
            #include <ctime>
            using namespace std;
            const int MAX = 105;
            int st[105];
            int N, x, y, w;
            struct vv {
                   int x, y, val;
                   void set ( int a, int b, int w ) { x=a,y=b,val=w; }
            
            }v[10005];       
            bool cmp ( const vv &a, const vv &b ) {
                      return a.val < b.val;     
            }
            void creat () {
                 for ( int i = 0; i <= N; ++ i )
                      st[i] = i;     
            }
            int find ( int x ) {
                return x != st[x] ? find ( st[x] ) : x;    
            }
            void merge ( int x, int y ) {
                 x = find ( x );
                 y = find ( y );
                 if ( x == y ) return;
                 st[y] = x;     
            }
            int main ()
            {
                while ( scanf ( "%d", &N )==1) {
                       creat ();
                       memset ( v, 0, sizeof ( v ) );
                       int c = 0;
                       for ( int i = 1; i <= N; ++ i ) {
                            for ( int j = 1; j <= N; ++ j ) {
                                 scanf ( "%d", &w );  
                                 v[c++].set ( i,j,w );  
                            }    
                       }     
                       sort ( v, v + c, cmp );
                       int sum = 0;
                       for ( int i = 0 ; i < c; ++ i ) {
                            if ( find ( v[i].x ) != find ( v[i].y ) ) {
                                sum += v[i].val;  
                                merge ( v[i].x, v[i].y );
                            }    
                       }
                       printf ( "%d\n", sum );
                }
                return 0;
            }
            

             

            久久久久国产精品三级网| 欧美精品久久久久久久自慰| 久久精品国产亚洲av高清漫画| 99久久人妻无码精品系列| 精品人妻伦九区久久AAA片69| 欧美一级久久久久久久大片| 亚洲av伊人久久综合密臀性色| www.久久精品| 欧美日韩精品久久久免费观看| 久久99国产精品久久99| 午夜精品久久影院蜜桃| 亚洲国产精久久久久久久| 国产毛片欧美毛片久久久| 99久久婷婷国产一区二区| 亚洲AV无码久久寂寞少妇| 国产精品无码久久四虎| 久久精品国产99国产精品导航| 91精品无码久久久久久五月天 | 久久精品国产只有精品2020| 精品久久久久久国产免费了| 久久99精品久久久久久久久久| 少妇久久久久久被弄到高潮| 亚洲午夜精品久久久久久人妖| 99久久精品免费看国产一区二区三区| 91久久九九无码成人网站| 2021少妇久久久久久久久久| 欧美伊人久久大香线蕉综合| 久久人人爽人爽人人爽av | 久久中文字幕人妻丝袜| 国产精品内射久久久久欢欢| 精品国产91久久久久久久 | 久久国产精品偷99| 亚洲乱亚洲乱淫久久| 曰曰摸天天摸人人看久久久| 久久99精品国产| 久久综合久久综合久久| 亚洲精品高清久久| 成人国内精品久久久久影院VR| 91亚洲国产成人久久精品| 精品久久久久久99人妻| 久久综合色老色|