随笔-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ǎ崽 阅读(921) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理