HDU 1233 还是畅通工程

今天学的最小生成树，先放上这个裸的题。

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1233

Prim算法

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 int map[110][110],lowcost[110],visit[110];
 4 #define N 1000000
 5 int prim(int maxminum)
 6 {
 7     int i,sum,j,k,min;
 8     for(i=1;i<=maxminum;i++)
 9     {
10         lowcost[i]=map[1][i];
11         visit[i]=0;
12     }
13     sum=0;
14     visit[1]=1;
15     for(i=1;i<=maxminum;i++)
16     {
17         min=N;
18         for(j=1;j<=maxminum;j++)
19         {
20             if(visit[j]==0&&lowcost[j]<min)
21             {
22                 min=lowcost[j];
23                 k=j;
24             }
25         }
26         visit[k]=1;
27         if(min==N)
28         break;
29         sum+=min;
30         for(j=1;j<=maxminum;j++)
31         {
32             if(visit[j]==0&&map[k][j]<lowcost[j])
33             {
34                 lowcost[j]=map[k][j];
35             }
36         }
37     }
38     return sum;
39 }
40 int main()
41 {
42     int maxmax,maxminum,i,a,b,value,sum;
43     while(~scanf("%d",&maxminum))
44     {
45         if(maxminum==0)
46         break;
47         memset(map,N,sizeof(map));
48         maxmax=(maxminum*(maxminum-1))/2;
49         for(i=1;i<=maxmax;i++)
50         {
51             scanf("%d%d%d",&a,&b,&value);
52             if(value<map[a][b])
53             {
54                 map[a][b]=map[b][a]=value;
55             }
56         }
57         sum=prim(maxminum);
58         printf("%d\n",sum);
59     }
60     return 0;
61 }

Kruskal算法

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 int map[110],num,sum;
 5 struct node
 6 {
 7     int a;
 8     int b;
 9     int value;
10 }tax[20000];
11 int findx(int x)
12 {
13     while(x!=map[x])
14     {
15         x=map[x];
16     }
17     return x;
18 }
19 void merge(int x,int y,int z)
20 {
21     int tx=findx(x);
22     int ty=findx(y);
23     if(tx!=ty)
24     {
25         map[tx]=ty;
26         sum+=z;
27         num++;
28     }
29 }
30 int cmp(const void *a,const void *b)
31 {
32     return(*(node*)a).value>(*(node*)b).value?1:-1;
33 }
34 int main()
35 {
36     int maxminum,maxmax,i;
37      while(~scanf("%d",&maxminum))
38     {
39         if(maxminum==0)
40             break;
41         maxmax=(maxminum*(maxminum-1))/2;
42         for(i=0;i<=maxminum;i++)
43             map[i]=i;
44         for(i=0;i<maxmax;i++)
45             scanf("%d%d%d",&tax[i].a,&tax[i].b,&tax[i].value);
46             sum=0;
47             num=0;
48         qsort(tax,maxmax,sizeof(tax[0]),cmp);
49         for(i=0;i<maxmax&&num<maxminum-1;i++)
50         merge(tax[i].a,tax[i].b,tax[i].value);
51         printf("%d\n",sum);
52     }
53     return 0;
54 }