好最大边权最小生成树507stree.cpp

设计一个算法

#include <iostream>
#include <fstream>
using namespace std;

#include "time.h"
clock_t start,finish;
ifstream in("input.txt");
ofstream out("output.txt");


//定义类型图
void delete2Darray(int ** &x,int rows);
class Agraph
{
    public:
		Agraph(int v=1,int noedge=0);
		~Agraph(){delete2Darray(a,n+1);}
		Agraph &get(int v,int u,int noedge);   //v是顶点数，u是边数
		bool prim(int &result);
		void output();
	private:
		int NoEdge;
		int n;
		int e;
		int **a;
};
void make2Darray(int **&x,int rows,int cols);
Agraph::Agraph(int v,int noedge)
{
	n=v;
	e=0;
	NoEdge=noedge;
	make2Darray(a,n+1,n+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			a[i][j]=NoEdge;
}
Agraph &Agraph::get(int v,int u,int noedge) 
{
	int x,y,w;
	n=v;
	e=u;
	NoEdge=noedge;
	make2Darray(a,n+1,n+1);	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			a[i][j]=noedge;
	for(i=0;i<u;i++)
	{
		in>>x>>y>>w;
		a[x][y]=w;
		a[y][x]=w;
	}

	return *this;
}
void Agraph::output()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			cout<<a[i][j]<<" ";
		cout<<endl;
	}
}
void delete2Darray(int ** &x,int rows)
{
	for(int i=0;i<rows;i++)
		delete[]x[i];
	delete []x;
	x=0;
}
void make2Darray(int **&x,int rows,int cols)
{
	x=new int *[rows];
	for(int i=0;i<rows;i++)
		x[i]=new int[cols];
}

//存放边结点
class edgenode
{
	friend void main(void);
	private:
		int weight; //边权
		int u,v;  //与边相关联的2个顶点
};
bool Agraph::prim(int &result)
{
	int i,j,k,kk=0;
	int *lowcost=new int[n+1];
	int *closest=new int[n+1];
	bool *s=new bool[n+1];

	s[1]=true;
	for(i=2;i<=n;i++)
	{
		lowcost[i]=a[1][i];
		closest[i]=1;
		s[i]=false;
	}
	for(i=1;i<n;i++)
	{
		int min=NoEdge;
		j=1;
		for(k=2;k<=n;k++)
			if((lowcost[k]<min)&&(!s[k]))
			{
				min=lowcost[k];
				j=k;
			}
		if(min==NoEdge)return false;
		if(result<lowcost[j])result=lowcost[j];
		s[j]=true;
		kk++;
		for(k=2;k<=n;k++)
			if((a[j][k]<lowcost[k])&&(!s[k]))
			{
				lowcost[k]=a[j][k];
				closest[k]=j;
			}
	}
	return (kk==n-1);
}

void main()
{
	start=clock();
	if(in.fail())
	{
		cout<<"the input.txt is not exist!";
		exit(1);
	}
	int n,m,result=0;      //存最大边权
	bool a;
	in>>n>>m;
	Agraph aa;
	aa.get(n,m,30000);
	a=aa.prim(result);
	if(a==false)out<<"-1";
	else out<<result;
	finish=clock();
	cout<<finish-start;
}