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

            USACO Section 3.1 Agri-Net

            Agri-Net

            Russ Cox

            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.

            PROGRAM NAME: agrinet

            INPUT FORMAT

            Line 1: The number of farms, N (3 <= N <= 100).
            Line 2..end: The subsequent lines contain the N x N connectivity 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.

            SAMPLE INPUT (file agrinet.in)

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

            OUTPUT FORMAT

            The single output contains the integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.

            SAMPLE OUTPUT (file agrinet.out)

            28
            Analysis

            A very traditional MST problem. Just use the Prim algorithm can get though it. Here I provide some simple descriptions about the Prim algorithm.
            The Prim algorithm plans to add a shortest path to the set A, which records the MST, and abandon the edge composed a cycle.

            Code

            /*
            ID:braytay1
            PROG:agrinet
            LANG:C++
            */

            #include 
            <iostream>
            #include 
            <fstream>
            using namespace std;
                
            int N;
            int map[101][101];
            int pi[101],key[101];
            bool Q[101];
            int min(int *a,bool *b){
                
            int res=10000000,mini;
                
            for (int i=0;i<N;i++){
                    
            if (res>*(a+i)&&*(b+i)==false{res=*(a+i);mini=i;}
                }

                
            return mini;
            }

            bool isempty(bool *a){
                
            for (int i=0;i<N;i++){
                    
            if (!*(a+i)) return false;
                }

                
            return true;
            }

            void prim(int g[101][101],int r){
                
            for (int u=0;u<N;u++){
                    key[u]
            =1000000;
                    pi[u]
            =0;
                    Q[u]
            =false;
                }

                key[r]
            =0;
                
            int u1;
                
            while (!isempty(Q)){
                    u1
            =min(key,Q);
                    Q[u1]
            =true;
                    
            for (int v=0;v<N;v++){
                        
            if (g[u1][v]&&Q[v]==false&&g[u1][v]<key[v]) {pi[v]=u1;key[v]=g[u1][v];}
                    }
                    
                }

            }

            int main(){
                ifstream fin(
            "agrinet.in");
                ofstream fout(
            "agrinet.out");
                fin
            >>N;
                
            for (int i=0;i<N;i++)
                    
            for (int j=0;j<N;j++){
                        fin
            >>map[i][j];
                    }

                prim(map,
            0);
                
            int res=0;
                
            for (int i=0;i<N;i++) res+=key[i];
                fout
            <<res<<endl;
                
            return 0;
            }


             

            posted on 2008-08-20 15:05 幻浪天空領主 閱讀(259) 評論(0)  編輯 收藏 引用 所屬分類: USACO

            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            精品无码久久久久久久动漫 | 久久国产免费直播| 性做久久久久久久久| 2019久久久高清456| 亚洲国产精品成人久久| 久久99国产综合精品女同| 久久免费美女视频| 伊人久久大香线蕉精品不卡| 无码AV波多野结衣久久| 国产福利电影一区二区三区久久久久成人精品综合 | 久久综合欧美成人| 欧美精品九九99久久在观看| 精品久久久久久无码专区| 国产精品嫩草影院久久| 少妇久久久久久久久久| 精品久久人人妻人人做精品| 无码AV中文字幕久久专区| 久久久WWW成人| 久久se精品一区精品二区| 久久久久久国产精品免费免费 | 精品多毛少妇人妻AV免费久久| 久久人人爽人人爽人人片AV麻烦| 四虎国产永久免费久久| 久久精品国产亚洲av日韩| 伊人精品久久久久7777| 久久精品成人| 国产高清美女一级a毛片久久w| 熟妇人妻久久中文字幕| 狠狠色丁香婷婷久久综合| 国产精品成人久久久久久久| 日日噜噜夜夜狠狠久久丁香五月 | 一级做a爰片久久毛片16| 久久九九精品99国产精品| 久久天天躁夜夜躁狠狠| 四虎久久影院| 亚洲精品无码久久不卡| 久久亚洲国产精品五月天婷| 久久国产高清一区二区三区| 色综合久久综精品| 久久高清一级毛片| 亚洲日韩欧美一区久久久久我|