• <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原創, 轉帖請注明 : 轉載自 ______________白白の屋    

             

            題目地址:

            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久久国产宗和精品1上映| 99久久国语露脸精品国产| 国产亚洲色婷婷久久99精品91| 亚洲国产精品无码久久久久久曰| 久久久国产亚洲精品| 久久精品国内一区二区三区| 色婷婷久久久SWAG精品| 久久久久久亚洲Av无码精品专口| 国产2021久久精品| 久久夜色精品国产欧美乱| 亚洲国产综合久久天堂| 国内精品久久久久久99蜜桃| 国产69精品久久久久9999APGF| 国产亚洲欧美成人久久片| 久久久久久精品免费看SSS| 亚洲一区中文字幕久久| 情人伊人久久综合亚洲| 久久久久综合网久久| 久久综合久久美利坚合众国| 亚洲国产成人精品女人久久久 | 久久精品成人欧美大片| 品成人欧美大片久久国产欧美| 亚洲午夜久久久久久噜噜噜| 观看 国产综合久久久久鬼色 欧美 亚洲 一区二区| 精品国产热久久久福利| 久久被窝电影亚洲爽爽爽| 嫩草伊人久久精品少妇AV| 天堂无码久久综合东京热| 精品99久久aaa一级毛片| 久久99国产精品99久久| 久久A级毛片免费观看| 婷婷久久久亚洲欧洲日产国码AV| 久久精品国产精品亚洲精品| 7777精品伊人久久久大香线蕉| 亚洲精品NV久久久久久久久久| 久久国产免费直播| 一本久久a久久精品亚洲| 精品久久亚洲中文无码|