POJ1258简单最小生成树

#include<stdio.h>
#include<algorithm>


#define N (100 + 10)


using namespace std;


typedef struct
{
   int x ,y ,c;
}NODE;


NODE node[N*N];
int  map[N][N];
int  mer[N];


int finds(int x)
{
   return x == mer[x] ? x : mer[x] = finds(mer[x]);
}


bool camp(NODE a ,NODE b)
{
   return a.c < b.c;
}


int main ()
{
   int n ,i ,j;
   while(~scanf("%d" ,&n))
   {
      int nowid = 0;
      for(i = 1 ;i <= n ;i ++)
      {
         for(j = 1 ;j <= n ;j ++)
         scanf("%d" ,&map[i][j]);
         for(j = i + 1 ;j <= n ;j ++)
         {
            nowid++;
            node[nowid].c = map[i][j];
            node[nowid].x=  i ,node[nowid].y = j;
         }
         mer[i] = i;
      }
      
      int Ans = 0 ,sum = 0;
      sort(node + 1 ,node + nowid + 1 ,camp);
      for(i = 1 ;i <= nowid ;i ++)
      {
         if(node[i].x == node[i].y) continue;
         int xx = finds(node[i].x);
         int yy = finds(node[i].y);
         if(xx != yy) Ans += node[i].c ,sum ++ ,mer[xx] = yy;
         if(sum == n - 1) break;
      }
      printf("%d " ,Ans);
   }
   return 0;
}