最小生成树之prim---zoj_1586

       在一个具有几个顶点的连通图G中，如果存在子图G'包含G中所有顶点和一部分边，且不形成回路，则称G'为图G的生成树，代价最小生成树则称为最小生成树。

　　许多应用问题都是一个求无向连通图的最小生成树问题。例如：要在n个城市铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

      算法为贪心思想，每次将距离最近的一个顶点入MST中，然后对剩余的顶点做松弛操作。MST算法可以使用有限队列来实现，使用二叉堆O(VlogV+ElogV),使用FIB-heapO(VlogV+E)，但是使用优先队列的实现比较适合与稀疏图。稠密图只要维护一个数组存储每个点的距离即可效率为O(V*V+E).

下面代码为zoj_1586的解

稠密图：

  

#include <iostream>
#include<stdio.h>
#define  DEBUG 1
using namespace std ;

const int Max=0x7fffffff ;
const int MaxSize=1001 ;
int map[MaxSize][MaxSize], dis[MaxSize], cost[MaxSize] ;
bool used[MaxSize] ;
int n ;
long long len ;

void init( )
{
    int i ;
    for( i=0; i<MaxSize; ++i )
        used[i] = false ;
    len = 0 ;
}

void Prim( )
{
    int Min, index, i, j ;
    for( i=1; i<=n; ++i ){
        dis[i] = map[1][i] ;
    }
    used[1] = true ;
    for( i=1; i<n; ++i ){
        Min = Max ;
        for( j=1; j<=n; ++j ){
            if( !used[j] && Min>dis[j] ){
                index = j ;
                Min = dis[j] ;
            }
        }
        used[index] = true ;
        len += dis[index] ;
        for( j=1; j<=n; ++j ){
            if( !used[j] && dis[j]>map[index][j] )
                dis[j] = map[index][j] ;
        }
    }
}

int main()
{
  	#if DEBUG
    freopen("e:\\zoj\\zoj_1586.txt","r",stdin) ;
    #endif
    
    int sets, i, j, distance ;
    scanf("%d", &sets ) ;
    while( sets-- ){
        init( ) ;
        scanf("%d", &n ) ;
        for( i=1; i<=n; ++i )
            scanf("%d", &cost[i] ) ;
        for( i=1; i<=n; ++i ){
            for( j=1; j<=n; ++j ){
                scanf("%d", &distance ) ;
                map[i][j] = distance+cost[i]+cost[j] ;
            }
        }
        Prim( ) ;
        printf("%lld\n", len ) ;
    }
    return 0 ;
}

 稀疏图：

#include<iostream>
#include<string.h>
#include<fstream>
using namespace std;
class node
{
public:
	int key,value;
	node()
	{
		key=-1;
		value=-1;	
	}
};
class priority_queue
{
public:
	const static int maxm=1005;
	node array[maxm];
	int index[maxm];
	int flag;
	priority_queue()
	{
		this->flag=0;
	}
	priority_queue(int flag)
	{
		this->flag=flag-1;
	}
	void heapify_MIN()
	{
		int n=flag/2+flag%2-1;
		for(int i=n;i>=0;i--)
		buildHeap_MIN(i,flag);
	}	
	void buildHeap_MIN(int k,int m)
	{
	
		int j=2*k+1;
		if(j>m)
			return;
		if(j+1<=m&&array[j].value>array[j+1].value)
			j=j+1;
		if(array[k].value>array[j].value)
		{
			int a=array[k].key;
			int b=array[j].key;
			index[a]=j;
			index[b]=k;
			node temp=array[k];
			array[k]=array[j];
			array[j]=temp;	
			buildHeap_MIN(j,m);
		}
	}
	node extract_MIN()
	{
		node res=array[0];
		int a=array[0].key;
		int b=array[flag].key;
		index[a]=flag;
		index[b]=0;
		node temp=array[0];
		array[0]=array[flag];
		array[flag]=temp;
		this->flag--;
		buildHeap_MIN(0,flag);
		return res;
	}
	void decrease_key(int k,int key)
	{
		if(k==0&&key<array[k].value)
		{
			array[k].value=key;
			return;
		}	
		if(array[k].value<=key)
			return;
		else
		{
			int n=k/2+k%2-1;
			if(array[n].value>key)
			{
				int a=array[k].key;
				int b=array[n].key;
				index[a]=n;
				index[b]=k;	
				node temp=array[k];
				array[k]=array[n];
				array[n]=temp;	
				decrease_key(n,key);
			}
			else
			{	
				array[k].value=key;
				return;
			}
		}
	}
};
int cases,n,dist;
const int maxm=10000;
int graphMatrix[1001][1001];
int favorate[1001];
int s[1001];
int path[1001];
int main()
{
	/*ifstream txtfile;
	txtfile.open("e:\\zoj\\zoj_1586.txt");
	if(!txtfile)
	{
		cerr<<"open error"<<endl;
		exit(1);
	}
	txtfile>>cases;*/
	cin>>cases;
	while(cases--)
	{
		//txtfile>>n;
		cin>>n;
		for(int i=0;i<n;i++)
		{
			//txtfile>>favorate[i];
			cin>>favorate[i];		
		}
		//memset(graphMatrix,0,sizeof(graphMatrix));
		memset(s,0,sizeof(s));
		for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{	
			//txtfile>>dist;
			cin>>dist;
			graphMatrix[i][j]=dist+favorate[i]+favorate[j];
		}
		priority_queue q(n-1);
		for(int i=1;i<n;i++)
		{
			path[i]=0;			
			s[i]=0;
		}
		path[0]=0;
		s[0]=1;
		for(int i=0;i<n-1;i++)
		{
			q.array[i].value=graphMatrix[0][i+1];
			q.array[i].key=i+1;
		}
		for(int i=1;i<n;i++)
		{
			q.index[i]=i-1;	
		}
		q.heapify_MIN();
		int result=0;
		for(int i=1;i<n;i++)
		{
			node p=q.extract_MIN();
			s[p.key]=1;
			result+=p.value;
			//cout<<p.key<<" ";
			for(int j=1;j<n;j++)
			{
				if(s[j]==0&&j!=p.key)
				{
					int index=q.index[j];
					if(graphMatrix[p.key][j]<q.array[index].value)
					{
						q.decrease_key(index,graphMatrix[p.key][j]);
						path[j]=p.key;	
					}
				}
			}			
		}
		//cout<<endl;
		cout<<result<<endl;
	}
	return 0;
}