细草微风岸

平凡而不平庸

常用链接

统计

最新评论

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)<=&& !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   知识库   博问   管理