• <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>
            心如止水
            Je n'ai pas le temps
            posts - 400,comments - 130,trackbacks - 0

            先把必要的邊連接在一起,將一條邊的頂點合并在同一個集合中,從剩余的邊中選擇權值最少的使圖連通即可。
            以下是我的代碼:

            #include<iostream>
            #define maxn 2007
            #define maxm 10007
            using namespace std;

            typedef 
            struct
            {
                
            long u,v,w;
            }edge;
            long n,m,cnt,num,ans,f[maxn];
            edge e[maxm];

            void Qsort(long l,long r)
            {
                
            long i=l,j=r,m=e[(l+r)/2].w;
                
            do{
                    
            while(e[i].w<m) i++;
                    
            while(e[j].w>m) j--;
                    
            if(i<=j)
                    {
                        edge t
            =e[i];e[i]=e[j];e[j]=t;
                        i
            ++;j--;
                    }
                }
            while(i<=j);
                
            if(l<j) Qsort(l,j);
                
            if(i<r) Qsort(i,r);
            }

            long Getf(long x)
            {
                
            if(f[x]==x) return x;
                f[x]
            =Getf(f[x]);
                
            return f[x];
            }

            int main()
            {
                cin
            >>n>>m;
                
            for(long i=1;i<=n;i++) f[i]=i;
                ans
            =num=cnt=0;
                
            for(long i=1;i<=m;i++)
                {
                    
            long ra,rb,rc,rd;
                    cin
            >>ra>>rb>>rc>>rd;
                    
            if(ra==1)
                    {
                        ans
            +=rd;
                        
            long fx=Getf(rb),fy=Getf(rc);
                        
            if(fx!=fy)
                        {
                            f[fx]
            =fy;
                            num
            ++;
                        }
                    }
                    
            else
                    {
                        cnt
            ++;
                        e[cnt].u
            =rb;e[cnt].v=rc;e[cnt].w=rd;
                    }
                }
                
            //  Input
                
                Qsort(
            1,cnt);
                
            //  Qsort
                
                
            for(long i=num,j=1;i<n-1;j++)
                {
                    
            long fx=Getf(e[j].u),fy=Getf(e[j].v);
                    
            if(fx!=fy)
                    {
                        f[fx]
            =fy;
                        ans
            +=e[j].w;
                        i
            ++;
                    }
                }
                
                cout
            <<ans<<endl;
                
            return 0;
            }
            posted on 2010-10-17 13:37 lee1r 閱讀(306) 評論(0)  編輯 收藏 引用 所屬分類: 題目分類:圖論
            久久国产高潮流白浆免费观看| 精品亚洲综合久久中文字幕| 久久精品国产亚洲7777| 狠狠人妻久久久久久综合| 久久精品国产欧美日韩99热| 久久w5ww成w人免费| 久久久久人妻精品一区三寸蜜桃| 久久久久噜噜噜亚洲熟女综合| 欧美亚洲色综久久精品国产| 九九久久精品国产| 久久ZYZ资源站无码中文动漫| 久久人人爽人人澡人人高潮AV | 精品久久久久中文字| 欧美精品国产综合久久| 国产成人久久久精品二区三区| 久久只这里是精品66| 国内精品久久久久久久久| 99久久国产精品免费一区二区| 久久91精品综合国产首页| 国产成年无码久久久久毛片| 国产成人精品综合久久久久| 久久人人爽人人爽人人片AV麻豆| 久久精品这里热有精品| 久久亚洲精品成人av无码网站| 亚洲人成网站999久久久综合| 国内精品久久久久久久亚洲| 日本免费一区二区久久人人澡 | 国产福利电影一区二区三区久久老子无码午夜伦不 | 天天影视色香欲综合久久| 国产高清美女一级a毛片久久w | 91久久精品91久久性色| 久久精品国产亚洲AV蜜臀色欲| 欧美日韩中文字幕久久久不卡| 国产激情久久久久影院| 狠狠久久综合| 久久这里只有精品首页| 久久精品国产亚洲av麻豆蜜芽| 国产国产成人精品久久| 无码专区久久综合久中文字幕| 欧美精品乱码99久久蜜桃| 久久综合久久综合亚洲|