2013寒假ACM集训_最小生成树

普里姆算法（稠密图）克鲁斯卡尔算法（稀疏图）

1.prime 算法

贪心集合加点

2. Kruskal算法

并查集加边

http://acm.hdu.edu.cn/showproblem.php?pid=1233

思想是加点，在边比较多的情况下，用prime。

思路：先找任意一点到其他的点的最短距离，再找这个点和刚才的点到其他的点的最短距离，依次重复

最小生成树(prime模版）

 1 #include<stdio.h>
 2   int grah[100][100];
 3   int sum=0;
 4   void pim(int n)
 5   {
 6       int i,j,pos;
 7       int min,v[100]={0},d[100];
 8       for(i=1;i<=n;i++)
 9           d[i]=grah[1][i];//  初始d代表1到i的值
10       v[1]=1;
11       for(i=2;i<=n;i++)
12       {
13           min=999999;
14           for(j=1;j<=n;j++)
15           {
16              if(!v[j]&&min>d[j])
17              {min=d[j];pos=j;}//找一个距离最小的点
18           }
19           sum+=min;
20           v[pos]=1;//标记已访问
21           for(j=1;j<=n;j++)
22           {
23               if(!v[j])
24               {
25                   if(d[j]>grah[pos][j])  // 如果以前的点到 这个点的距离小，就用以前的距离 
26                       d[j]=grah[pos][j]; //现在的d代表的是 所有已标记的点 到其他点的最短距离
27               }
28           }
29       }
30       
31   }
32   int main()
33   {
34       int n,i,j;  
35       int x,y,z;
36       while(scanf("%d",&n),n)
37       {
38       
39           for(i=1;i<=n;i++)
40            for(j=1;j<=n;j++)
41                grah[i][j]=999999;
42            for(i=1;i<=n;i++)
43               grah[i][i]=0;
44            int k=(n*(n-1))/2;
45            while(k--)
46            {
47         scanf("%d%d%d",&x,&y,&z);
48         grah[x][y]=grah[y][x]=z;//初始都等于z;
49            }
50         pim(n);
51         printf("%d\n",sum);
52         sum=0;
53       }
54       return 0;
55   }

/*HDU hdu 1233 还是畅通工程

最小生成树(kruskal模版）

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 int bin[101],sum,num;
 5 struct node
 6 {
 7     int u;
 8     int v;
 9     int w;
10 }p[10000];
11 int cmp(const void *a,const void *b)
12 {
13     return (*(struct node *)a).w > (*(struct node *)b).w ? 1:-1;
14 }
15 int find(int x)
16 {
17     int r = x,t;
18     while(x != bin[x])
19     x = bin[x];
20     while(x != r)
21     {
22         t = bin[r];
23         bin[r] = x;
24         r = t;
25     }
26     return x;
27 }
28 void merge(int x,int y,int w)
29 {
30     x = find(x);
31     y = find(y);
32     if(bin[x] != y)
33     {
34         bin[x] = y;
35         sum += w;
36         num ++;
37     }
38 }
39 int main()
40 {
41     int i,n;
42     while(~scanf("%d",&n)&&n!=0)
43     {
44         sum = 0;num = 1;
45         for(i = 1;i <= n;i ++)
46             bin[i] = i;
47 
48         for(i = 0;i <= n*(n-1)/2-1;i ++)
49         {
50             scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].w);
51         }
52         qsort(p,n*(n-1)/2,sizeof(p[0]),cmp);
53         for(i = 0;i <= n*(n-1)/2-1;i ++)
54         {
55             merge(p[i].u,p[i].v,p[i].w);
56             if(num == n) break;
57         }
58         printf("%d\n",sum);
59     }
60     return 0;
61 }