细草微风岸

平凡而不平庸

常用链接

统计

最新评论

PKU_1258 MST

//Kruskal
#include<iostream>
#include<algorithm>
using namespace std;
#define clr(a) memset(a,-1,sizeof(a))
#define MAXN 101
#define INF 100001
int dis[MAXN][MAXN];
//Kruskal,
//并查集
int parent[MAXN];
int rank[MAXN];
int A[MAXN*MAXN/2];
int e_X[MAXN*MAXN/2];
int e_Y[MAXN*MAXN/2];
int d[MAXN*MAXN/2];
void MakeSet(int x)
{
  parent[x] = x;
  rank[x] = 0;
}
int Find(int x)
{
    if(parent[x] == x)
        return x;
    else 
    {
       parent[x] = Find(parent[x]);// 路径压缩
       return parent[x];
    }
}
void Union(int x,int y)
{
  int xRoot = Find(x);
  int yRoot = Find(y);
  if(rank[xRoot] > rank[yRoot])// rank优化
      parent[yRoot] = xRoot;
  else if(rank[xRoot] < rank[yRoot])
      parent[xRoot] = yRoot;
  else if(xRoot != yRoot)
  {
     parent[yRoot] = xRoot;
     rank[xRoot] += 1;
  }

} 
//最小堆先自己写，熟练后用STL的优先队列
void sift_up(int i)
{
   bool done = false;
   int temp;
   if(i == 1)
       return;
   while(i!=1 && !done)
   {
     if(d[A[i]]<d[A[i/2]])
     {
         temp = A[i];
         A[i] = A[i/2];
         A[i/2] = temp;
     }
     else
         done = true;
     i /= 2;

   }
}
void sift_down(int i,int n)
{
   bool done = false;
   int temp;
   if((2*i) > n)
       return;
   while((2*i)<=n && !done)
   {
      i *= 2;
      if((i+1) <= n && d[A[i+1]] < d[A[i]])
          i += 1;
      if(d[A[i/2]] > d[A[i]])
      {
        temp = A[i/2];
        A[i/2] = A[i];
        A[i] = temp;
      }
      else
          done = true;
   }
}
void Delete(int i, int& n)
{
   int x = A[i];
   int y = A[n];
   n -= 1;
   if(i == (n+1))
       return;
   A[i] = y;
   if(d[y] <= d[x])
       sift_up(i);
   else 
       sift_down(i,n);
}
int delete_min(int& n)
{
   int x = A[1];
   Delete(1,n);
   return x;
}
void MakeHeap(int n)
{
    int i ;
    for(i = n/2; i >= 1; i--)
    {
       sift_down(i,n);
    }
}
int Kruskal(int n)
{
    int i,j,count=0,ans=0,x; 
    clr(parent);
    clr(rank);
    int k = 1;
    for(i = 0; i < n;i++)
        for(j = i+1; j < n;j++)
        {
           d[k] = dis[i][j];
           e_X[k] = i;
           e_Y[k] = j;
           A[k] = k;
           k++;
        }
    MakeHeap(k-1);
    for(i = 0; i < n; i++)
        MakeSet(i);
    int N = k-1;
    while(count < (n-1))
    {
       x = delete_min(N);
       if(Find(e_X[x])!= Find(e_Y[x]))
       {
          count++;
          ans += d[x];
          Union(e_X[x],e_Y[x]);
       }
    }
    return ans;    
}
int main()
{
   int n,i,j;
   while(scanf("%d",&n)!=EOF)
   {
     for(i = 0; i < n;i++)
         for(j = 0; j < n; j++)
            scanf("%d",&dis[i][j]);
     printf("%d\n",Kruskal(n));
   }
}

//Prim:
#include<iostream>
#include<algorithm>
using namespace std;
#define clr(a) memset(a,-1,sizeof(a))
#define MAXN 101
#define INF 100001
int dis[MAXN][MAXN];
//prim
int C[MAXN];
int N[MAXN];
int visit[MAXN];
int prim(int n)
{
    int i,j,k,min,ans=0;
    //首先选择第个点作为起始点
    for(i = 0; i < n;i++)
    {
      C[i] = dis[i][0];
      //N[i] = 0;
      visit[i] = 0;
    }
    visit[0] = 1;
    for(i = 0; i < (n-1); i++)
    {
       min = INF;
       for(j = 0; j < n;j++)
       {
           if(C[j] < min && visit[j] == 0)
           {
             min = C[j];
             k = j;//此处肯定有最小值，因为每条边都存在。
           }
       }
       visit[k] = 1;//加入新的点
       ans += C[k];
       for(j = 0;j < n;j++)
       {
           if(visit[j] == 0 && C[j] > dis[k][j])
           {
               C[j] = dis[k][j];
               N[j] = k;
           }
       }
    }
    return ans;
}
int main()
{
   int n,i,j;
   while(scanf("%d",&n)!=EOF)
   {
     for(i = 0; i < n;i++)
         for(j = 0; j < n; j++)
            scanf("%d",&dis[i][j]);
     printf("%d\n",prim(n));
   }
}






posted on 2011-07-27 00:08 鲍青 阅读(138) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理