int n;    //结点数量

int s[MAX][MAX]; //图

int tree[MAX][MAX]; //生成树图,s[i][j]=0表示i与j之间不通

int visit[MAX]; //标记是否访问

int root[MAX]; //标记每棵生成树的根

int Prim(int &degree)

{

   degree = 0;

   int ans = 0;

   int cost[MAX];

   memset(visit, 0, sizeof(visit));

   memset(tree, 0, sizeof(tree));

   memset(root, 0, sizeof(root));

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

   {

      if(visit[i] == 0)

      {

         root[++degree] = i;

         visit[i] = degree;

         memset(cost, 0, sizeof(cost));

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

         {

            if(j != i && visit[j] == 0 && s[i][j] != 0)

            {

               cost[j] = i;

            }

         }

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

         {

            int min = 0x7FFFFFFF;

            int tmp = -1;

            for(int k = 1; k <= n; ++k)

            {

               if(visit[k] == 0 && cost[k] != 0)

               {

                  if(s[cost[k]][k] < min)

                  {

                     min = s[cost[k]][k];

                     tmp = k;

                  }

               }

            }

            if(tmp == -1) break;

            tree[cost[tmp]][tmp] = tree[tmp][cost[tmp]] = s[cost[tmp]][tmp];

            visit[tmp] = degree;

            ans += s[cost[tmp]][tmp];

            for(int k = 1; k <= n; ++k)

            {

               if(k != tmp && visit[k] == 0 && s[k][tmp] != 0)

               {

                  if(cost[k] == 0)

                  {

                     cost[k] = tmp;

                  }

                  else if(s[k][tmp] < s[cost[k]][k])

                  {

                     cost[k] = tmp;

                  }

               }

            }

         }

      }

   }

   return ans;

}