• <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>
            隨筆-72  評論-126  文章-0  trackbacks-0
            HDU的最小數題目:
            1301
            1233
            1863
            1162
            1879
            1875
            昨天就一直在做這類題目,但一直以為是最短路,其實很像
            我昨天的做法其實就是prime算法
            http://acm.hdu.edu.cn/showproblem.php?pid=1233為例子
            #include<stdio.h>
            #define inf 0x7FFFFFFF
            #define M 100
            int map[M][M];
            int link[M];
            bool visit[M];
            int main()
            {
                
            int n,m,a,b,i,j,dis,min,cnt;
                
            while (scanf("%d",&n),n)
                {
                    
            for(i=1;i<=n;i++)
                    {
                        visit[i] 
            = 1;
                        
            for(j=1;j<=n;j++)
                            map[i][j] 
            = inf;
                    }
                    m 
            = n*(n-1)/2;
                    
            while(m--)
                    {
                        scanf(
            "%d%d%d",&a,&b,&dis);
                        map[a][b] 
            = map[b][a] = dis;
                    }
                    cnt 
            = 1;
                    link[
            0= 1;
                    visit[
            1= 0;
                    dis 
            = 0;
                    
            while(cnt != n)
                    {
                        min 
            = inf;
                        
            for(i=0;i<cnt;i++)
                            
            for(j=1;j<=n;j++)
                            {
                                
            if(visit[j] && map[ link[i] ][j]<min)
                                {
                                    link[cnt] 
            = j;
                                    min 
            = map[ link[i] ][j];
                                }
                            }
                        dis 
            += min;
                        visit[link[cnt]] 
            = 0;
                        cnt 
            ++;
                    }
                    printf(
            "%d\n",dis);
                }
                
            return 0;
            }

            今天學習了Kruskal,快捷很多,也就是 AekdyCoin大大說講的并查集寫的,不經效率高,寫的也快
            #include<stdio.h>
            #include
            <stdlib.h>
            #define M 101
            struct L{
                
            int a,b,dis;
            }road[M
            *(M-1)/2];
            int x[M];
            int find(int a)
            {
                
            int t,b=a;
                
            while(a!=x[a])
                    a 
            = x[a];
                
            while(b!=a)
                {
                    t 
            = x[b];
                    x[b] 
            = a;
                    b 
            = t;
                }
                
            return a;
            }
            int cmp(const void *a,const void *b)
            {
                
            return (*(struct L *)a).dis - (*(struct L *)b).dis;
            }
            int main()
            {
                
            int n,m,i,dis,cnt,a,b;
                
            while (scanf("%d",&n),n)
                {
                    m 
            = n*(n - 1)/2;
                    
            for(i=1;i<=n;i++)
                        x[i] 
            = i;
                    
            for(i=0;i<m;i++)
                        scanf(
            "%d%d%d",&road[i].a,&road[i].b,&road[i].dis);
                    qsort(load,m,
            sizeof(road[0]),cmp);
                    dis 
            = 0;
                    cnt 
            = 0;
                    
            for(i=0;cnt<n-1;i++)
                    {
                        a 
            = find(road[i].a);
                        b 
            = find(road[i].b);
                        
            if(a!=b)
                        {
                            dis 
            += road[i].dis;
                            x[a] 
            = b;
                            cnt 
            ++;
                        }
                    }
                    printf(
            "%d\n",dis);
                }
                
            return 0;
            }
            posted on 2009-02-16 11:18 shǎ崽 閱讀(926) 評論(0)  編輯 收藏 引用
            久久精品免费网站网| 天天久久狠狠色综合| 亚洲国产精品成人久久蜜臀| 日日狠狠久久偷偷色综合0| 久久久这里只有精品加勒比| 久久久久亚洲AV片无码下载蜜桃| 国产69精品久久久久777| 久久精品这里只有精99品| 成人久久免费网站| 国产福利电影一区二区三区久久老子无码午夜伦不 | 色99久久久久高潮综合影院| 99精品久久久久久久婷婷| 国产亚洲美女精品久久久久狼| 国产精品内射久久久久欢欢| 伊人久久大香线蕉AV色婷婷色| 日本精品久久久中文字幕| 久久亚洲国产精品成人AV秋霞| 久久久久久a亚洲欧洲aⅴ | 久久精品中文字幕无码绿巨人| 中文字幕成人精品久久不卡| 久久久久久久久波多野高潮| 久久精品国产WWW456C0M| 久久青青草原精品国产| 亚洲国产小视频精品久久久三级 | 99精品国产99久久久久久97 | 77777亚洲午夜久久多喷| 午夜肉伦伦影院久久精品免费看国产一区二区三区 | 色综合久久中文综合网| 人妻精品久久久久中文字幕69 | 99国产欧美精品久久久蜜芽 | 久久精品国产亚洲精品| AV无码久久久久不卡蜜桃| 狠狠综合久久综合88亚洲| 久久天天躁狠狠躁夜夜av浪潮| 久久国产一区二区| 999久久久免费精品国产| 中文国产成人精品久久不卡| 内射无码专区久久亚洲| 久久久久久国产a免费观看不卡 | 国产成人无码精品久久久性色 | 久久国产欧美日韩精品|