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

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

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

 #include <cstdio>

 #include <cstring>

 #include<cstdlib>

 #include<iostream>

 using namespace std ;

 #define oo (1<<28)

 const int N =  ;

 int map[N][N],low[N],flag[N];//low数组是用来保留最小代价的；

 //flag数组是用来标记的，找过得点就不再去找

 int m,n;

 int u,v,w ;

 int prim()

 {

     int i,j,pos,min,ans=;

     memset(flag,,sizeof(flag));

     flag[]=;

     pos=;

     for(i =  ; i <= n ; i++)

         if(i != pos)

             low[i] = map[pos][i];

     for(i =  ; i < n ; i++)

     {

         min=oo;

         for(j =  ; j <= n ; j++)

             if(flag[j] == &&min>=low[j])

             {

                 min = low[j];

                 pos = j ;

             }

         ans += min ;

         flag[pos] =  ;

         for(j =  ; j <= n ; j++)

             if(flag[j] == &&low[j]>map[pos][j])

                 low[j]=map[pos][j];

     }

     return ans;

 }

 int main()

 {

     int ans;

     while(scanf("%d %d",&n,&m)!=EOF)

     {

         for(int i =  ; i < N ; i++)

         {

             for(int j =  ; j < N ; j++)

             {

                 map[i][j] = oo ;

             }

         }

         for(int i =  ; i <= m ; i++)

         {

             scanf("%d %d %d",&u,&v,&w);

            if(map[u][v] >w)//防止重边出现保留小的重边

             map[u][v] = map[v][u] = w ;

         }

         ans = prim();

         printf("%d\n",ans);

     }

     return ;

 }

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 using namespace std ;

 const int MAXN =  ;

 const int MAX =  ;

 int EDG[MAX];

 int sum;

 struct node

 {

     int u ;

     int v ;

     int w ;

 } map[MAXN],t;

 int find(int x)

 {

     while(x!=EDG[x]){

         x=EDG[x];

     }

     return x;

 }

 void Kruskal(int x,int y,int z)

 {

     x = find(x) ;

     y = find(y) ;

     if(x != y)

     {

         EDG[x] = y ;

         sum += z;

     }

 }

 int main()

 {

     int n,m,i,j;

     while(~scanf("%d %d",&n,&m))

     {

         sum =  ;

         int k =  ;

         for(int i =  ; i <= n ; i++)

             EDG[i] = i ;

         for(int i =  ; i <= m ; i++)

             scanf("%d %d %d",&map[i].u,&map[i].v,&map[i].w);

         for(int i =  ; i <= m- ; i++){

             for(j = i+ ; j <= m ; j++){

                 if(map[i].w > map[j].w)

                 {

                     t = map[i] ;

                     map[i] = map[j];

                     map[j] = t ;

                 }

             }

         }

         for(int i =  ; i <= m ; i++)

             Kruskal(map[i].u,map[i].v,map[i].w);

             printf("%d\n",sum);

     }

     return ;

 }