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

            C小加

            厚德 博學 求真 至善 The bright moon and breeze
            posts - 145, comments - 195, trackbacks - 0, articles - 0
              C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

            poj 1251 NYOJ 434 Jungle Roads 解題報告

            Posted on 2011-11-05 19:44 C小加 閱讀(1353) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告
            題意:在相通n個島嶼的所有橋都壞了,要重修,重修每一個橋所用的時間不同,求重修使每個島嶼都間接或直接與其他島嶼相同時所用的的最短時間(只有修完一個橋后才可修下一個橋)。
            思路:10月份月賽唯一過的題。裸體的最小生成樹,我用的是Kruskal+并查集。
             
            #include 
            <iostream>
            #include 
            <algorithm>
            #include 
            <cstdio>
            #include 
            <cstring>
            using namespace std;
            const int MAX=27*27+1;
            typedef 
            struct
            {
                
            int a,b;
                
            int len;
            }node;

            node nod[MAX];
            int father[MAX];

            int cmp(node b1,node b2)
            {
                
            return b1.len<b2.len;
            }
            int find(int x)
            {
                
            return father[x]==x?x:father[x]=find(father[x]);
            }
            void Union(int a1,int a2)
            {
                father[a1]
            =a2;
            }
            int main()
            {
                
            int n;
                
            while(cin>>n&&n)
                {
                    memset(nod,
            0,sizeof(nod));
                    
            int i;
                    
            for(i=0;i<=MAX;i++)
                    {
                        father[i]
            =i;
                    }
                    
            int tempn=n,cnt=0;
                    tempn
            --;
                    
            while(tempn--)
                    {
                        
            string s1;
                        cin
            >>s1;
                        
            int qn;
                        cin
            >>qn;
                        
            if(qn==0continue;
                        
            while(qn--)
                        {
                            
            string s2;
                            cin
            >>s2;
                            
            int len;
                            cin
            >>len;
                            nod[cnt].a
            =s1[0]-'A'+1;
                            nod[cnt].b
            =s2[0]-'A'+1;
                            nod[cnt].len
            =len;
                            cnt
            ++;
                        }
                    }
                    sort(nod,nod
            +cnt,cmp);
                    
            int sum=0;
                    
            for(i=0;i<cnt;i++)
                    {
                        
            int x=find(nod[i].a);
                        
            int y=find(nod[i].b);
                        
            if(x==y)
                        
            continue;
                        
            else
                        {
                            Union(x,y);
                            sum
            +=nod[i].len;
                        }
                    }
                    cout
            <<sum<<endl;

                }
                
            return 0;
            }
                    

            亚洲精品WWW久久久久久 | 久久亚洲AV成人出白浆无码国产| 精品国产婷婷久久久| 人妻无码久久精品| 国产99久久久久久免费看| 精品国产VA久久久久久久冰| 色播久久人人爽人人爽人人片AV| 精品无码人妻久久久久久| 亚洲一区精品伊人久久伊人| 精品国产乱码久久久久久郑州公司 | 久久久久久亚洲Av无码精品专口 | 无码人妻少妇久久中文字幕蜜桃| 久久久精品国产Sm最大网站| 新狼窝色AV性久久久久久| 久久精品国产99久久久香蕉| 中文字幕乱码人妻无码久久| 97香蕉久久夜色精品国产| 日韩精品久久久久久| 99久久亚洲综合精品成人| 国产精品免费福利久久| 国产精品久久久久a影院| 丁香久久婷婷国产午夜视频| 久久99久久99精品免视看动漫| 无码乱码观看精品久久| 成人亚洲欧美久久久久| 久久国产精品无码一区二区三区 | 欧美久久综合性欧美| 久久精品国产亚洲av麻豆小说| 久久亚洲AV无码精品色午夜| 国内精品久久久久久久影视麻豆| 99久久久精品免费观看国产| 久久精品中文字幕无码绿巨人| 久久中文字幕精品| 97久久精品无码一区二区天美| 久久免费国产精品一区二区| 1000部精品久久久久久久久| www性久久久com| 国产精品久久自在自线观看| 99久久精品影院老鸭窝| 狠狠色丁香久久综合五月| 亚洲精品无码久久久|