最小生成树.cpp

图论的一些常用代码

/*
   pku 2485 Highways
  */
#include <iostream>  
using namespace std; 
#define MAXN 501
#define info 100000000
typedef int elemtype;
int prim(int mat[][MAXN],int n)
{
	elemtype lowcost[MAXN];
	int closest[MAXN],i,j,k,mini,ret=0,maxi=0;
	bool v[MAXN];
	for (i=0;i<n;i++)
	{
		lowcost[i]=mat[0][i];
		closest[i]=0;
		v[i]=false;
	}
	v[0] = true;
	for (i=0;i<n-1;i++)
	{
		k=0;
		mini=info;
		for (j=0;j<n;j++)
		{
			if (!v[j] && lowcost[j]<mini)
			{
				mini=lowcost[j];
				k=j;
			}
		}
		v[k]=true;
		if (maxi<lowcost[k])
			maxi = lowcost[k];
		ret+=lowcost[k];
		for (j=0;j<n;j++)
		{
			if (!v[j] && mat[k][j]<lowcost[j])
			{
				lowcost[j]=mat[k][j];
				closest[j]=k;	//树状的父结点，没啥用
			}
		}
	}
	return maxi;
}
int main() 
{ 
	freopen("in.txt","r",stdin);
	int i,j,n,k;
	int mat[MAXN][MAXN];
	cin>>n;
	for (k=0;k<n;k++)
	{
		int m;
		cin>>m;
		for (i=0;i<m;i++)
			for (j=0;j<m;j++)
				cin>>mat[i][j];
			cout<<prim(mat,m)<<endl;
	}	
	return 0 ; 
}