SDUT图结构练习——最小生成树

http://acm.sdut.edu.cn/sdutoj/showproblem.php?pid=2144&cid=1186

这道题一开始是用prim算法做的，一直错一直错，后来问了帅郭改用Kruskal做才对，再后来问了ＴＨＨ和二货才改对的prim算法，是因为重边我没处理啊，上火

 1 #include <cstdio>
 2 #include <cstring>
 3 #include<cstdlib>
 4 #include<iostream>
 5 using namespace std ;
 6 #define oo (1<<28)
 7 const int N = 110 ;
 8 int map[N][N],low[N],flag[N];//low数组是用来保留最小代价的；
 9 //flag数组是用来标记的，找过得点就不再去找
10 int m,n;
11 int u,v,w ;
12 int prim()
13 {
14     int i,j,pos,min,ans=0;
15     memset(flag,0,sizeof(flag));
16     flag[1]=1;
17     pos=1;
18     for(i = 1 ; i <= n ; i++)
19         if(i != pos)
20             low[i] = map[pos][i];
21     for(i = 1 ; i < n ; i++)
22     {
23         min=oo;
24         for(j = 1 ; j <= n ; j++)
25             if(flag[j] == 0&&min>=low[j])
26             {
27                 min = low[j];
28                 pos = j ;
29             }
30         ans += min ;
31         flag[pos] = 1 ;
32         for(j = 1 ; j <= n ; j++)
33             if(flag[j] == 0&&low[j]>map[pos][j])
34                 low[j]=map[pos][j];
35     }
36     return ans;
37 }
38 int main()
39 {
40     int ans;
41     while(scanf("%d %d",&n,&m)!=EOF)
42     {
43         for(int i = 1 ; i < N ; i++)
44         {
45             for(int j = 1 ; j < N ; j++)
46             {
47                 map[i][j] = oo ;
48             }
49         }
50         for(int i = 1 ; i <= m ; i++)
51         {
52             scanf("%d %d %d",&u,&v,&w);
53            if(map[u][v] >w)//防止重边出现保留小的重边
54             map[u][v] = map[v][u] = w ;
55         }
56         ans = prim();
57         printf("%d
",ans);
58     }
59     return 0;
60 }

View Code

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<iostream>
 5 using namespace std ;
 6 const int MAXN = 10000 ;
 7 const int MAX = 100 ;
 8 int EDG[MAX];
 9 int sum;
10 struct node
11 {
12     int u ;
13     int v ;
14     int w ;
15 } map[MAXN],t;
16 int find(int x)
17 {
18     while(x!=EDG[x]){
19         x=EDG[x];
20     }
21     return x;
22 }
23 void Kruskal(int x,int y,int z)
24 {
25     x = find(x) ;
26     y = find(y) ;
27     if(x != y)
28     {
29         EDG[x] = y ;
30         sum += z;
31     }
32 }
33 int main()
34 {
35     int n,m,i,j;
36     while(~scanf("%d %d",&n,&m))
37     {
38         sum = 0 ;
39         int k = 0 ;
40         for(int i = 1 ; i <= n ; i++)
41             EDG[i] = i ;
42         for(int i = 1 ; i <= m ; i++)
43             scanf("%d %d %d",&map[i].u,&map[i].v,&map[i].w);
44         for(int i = 1 ; i <= m-1 ; i++){
45             for(j = i+1 ; j <= m ; j++){
46                 if(map[i].w > map[j].w)
47                 {
48                     t = map[i] ;
49                     map[i] = map[j];
50                     map[j] = t ;
51                 }
52             }
53         }
54         for(int i = 1 ; i <= m ; i++)
55             Kruskal(map[i].u,map[i].v,map[i].w);
56             printf("%d
",sum);
57     }
58     return 0;
59 }

View Code