最小生成树 HDU 各种畅通工程的题，prim和kru的模板题

hdu 1879 继续畅通工程克鲁斯

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 typedef struct node
 5 {
 6     int u,v,w;
 7 }edge;
 8 edge e[10005];
 9 int dg[105];
10 void init(int n)
11 {
12     int i;
13     for(i = 1;i <=n ;i++)
14     dg[i] = i;
15 }
16 int cmp(const void *a,const void *b)
17 {
18     return (*(struct node *)a).w-(*(struct node *)b).w;
19 }
20 int find(int x)
21 {
22     if(x != dg[x])
23     {
24         dg[x] = find(dg[x]);
25     }
26     return dg[x];
27 }
28 
29 int main()
30 {
31     int n,i,j,leap,ans,u,v;
32     while(scanf("%d",&n)&&n)
33     {
34         int t = n*(n-1)/2;
35         ans = 0;
36         for(i = 1;i <= t;i++){
37             scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].w,&leap);
38             if(leap)
39             e[i].w = 0;
40         }
41 
42         qsort(e+1,t,sizeof(edge),cmp);
43         init(n);
44 
45         for(i = 1;i <= t;i++)
46         {
47             u = find(e[i].u);
48             v = find(e[i].v);
49             if(u != v)
50             {
51                 dg[u] = v;
52                 ans += e[i].w;
53             }//到这里就卡主了= =。。。
54         }
55         printf("%d\n",ans);
56     }
57     return 0;
58 }

View Code

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

1233 还是畅通工程 prim

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 int map[105][105];
 5 int vis[105];
 6 int d[105];
 7 int prime(int n)
 8 {
 9     int i,j,primer,ans,min;
10     memset(vis,0,sizeof(vis));
11     
12     ans = 0;
13     for(i = 2;i <= n;i++)
14     d[i] = map[1][i];
15     vis[1] = 1;
16 
17     for(i = 1;i < n;i++)
18     {
19         min = 0x7fffffff;
20         for(j = 2;j <= n;j++)
21         {
22             if(min > d[j]&& !vis[j])
23             min = d[j],primer = j;
24         }
25         ans += min;
26         vis[primer] = 1;
27         for(j = 2;j <= n;j++)
28         if(d[j] > map[primer][j] && !vis[j])
29         d[j] = map[primer][j];
30     }
31     return ans;
32 }
33 int main()
34 {
35     int n,w,i,j,leap,ans,u,v;
36     while(scanf("%d",&n)&&n)
37     {
38         int t = n*(n-1)/2;
39         ans = 0;
40 
41         for(i = 1;i <= n;i++)
42             for(j = 1;j <= n;j++)
43             map[i][j] = 0x7fffffff;
44 
45         for(j = 1;j <= n;j++)
46         map[j][j] = 0;
47 
48         for(i = 1;i <= t;i++){
49             scanf("%d%d%d",&u,&v,&w);
50             if(map[u][v]>w)
51             map[u][v] = map[v][u] = w;
52         }
53         ans = prime(n);
54         printf("%d\n",ans);
55     }
56     return 0;
57 }

kru

View Code

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

1863 畅通工程克鲁斯

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 typedef struct node
 5 {
 6     int u,v,w;
 7 }edge;
 8 edge e[10005];
 9 int set[105];
10 int cmp(const void *a,const void *b)
11 {
12     return (*(struct node*)a).w-(*(struct node*)b).w;
13 }
14 int find(int x)
15 {
16     if(x != set[x])
17     set[x] = find(set[x]);
18 }
19 void merge(int x,int y)
20 {
21     set[x] = y;
22 }
23 void init(int n)
24 {
25     int i;
26     for(i = 1;i <= n;i++)
27     set[i] = i;
28 }
29 int main()
30 {
31     int n,w,i,j,leap,ans,u,v,m;
32     while(scanf("%d %d",&n,&m)&&n)
33     {
34         init(m);
35         ans = 0;
36         for(i = 1;i <= n;i++)
37         scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);
38 
39         qsort(e+1,n,sizeof(edge),cmp);
40         for(i = 1;i <= n;i++)
41         {
42             u = find(e[i].u);
43             v = find(e[i].v);
44             if(u != v)
45             {
46                 merge(u,v);
47                 ans += e[i].w;
48             }
49         }
50 
51         int t;
52         t = find(1);
53         leap = 1;
54         for(i = 2;i <= m;i++)
55         {
56             set[i] = find(i);
57             if(t != set[i])
58             {
59                 leap = 0;
60                 break;
61             }
62         }
63 
64 
65 
66         if(leap)
67         printf("%d\n",ans);
68         else
69         puts("?");
70     }
71     return 0;
72 }