stree.cpp

对于给定的赋权图G

#include<iostream>
#include<fstream>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
//用邻接矩阵实现图
//用邻 接矩阵实现赋权有向图
template<class T> class AdjacencyWgraph;
template<class T>
class AdjacencyWdigraph
{
	friend AdjacencyWgraph<T>;
	public:
		AdjacencyWdigraph(int Vertices=10,T noEdge=0 );
		~AdjacencyWdigraph() { Delete2Darray(a,n+1); }
		bool Exist(int i,int j) const;
		int Edges() const { return e; }
		int Vertices() const { return n; }
		AdjacencyWdigraph<T> &Add(int i,int j,const T &w);
		AdjacencyWdigraph<T> &Delete(int i,int j);
		int OutDegree(int i) const;
		int InDegree(int i) const;
		void Output() const;
	private:
		T NoEdge;//无边标记
		int n;//顶点数
		int e;//边数
		T **a;//邻接矩阵
};
template<class T>
void Make2Darray(T ** &x,int rows,int cols)
{
	x=new T *[rows];
	for(int i=0;i<rows;i++)
		x[i]=new T[cols];
}
template<class T>
void Delete2Darray(T ** &x,int rows)
{
	for(int i=0;i<rows;i++)
		delete []x[i];
	delete []x;
	x=0;
}
template<class T>
AdjacencyWdigraph<T>::AdjacencyWdigraph(int Vertices,T noEdge)
{
	n=Vertices;
	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;
}
template<class T>
bool AdjacencyWdigraph<T>::Exist(int i,int j) const
{
	if(i<1||j<1||i>n||j>n||a[i][j]==NoEdge)
		return false;
	return true;
}
template<class T>
AdjacencyWdigraph<T> &AdjacencyWdigraph<T>::Add(int i,int j,const T &w)
{
	
	a[i][j]=w;
	e++;
	return *this;
}
template<class T>
AdjacencyWdigraph<T> &AdjacencyWdigraph<T>::Delete(int i,int j)
{
	
	a[i][j]=NoEdge;
	e--;
	return *this;
}
template<class T>
int AdjacencyWdigraph<T>::OutDegree(int i) const
{
	if(i<1||i>n) 
		throw BadInput();
	int sum=0;
	for(int j=1;j<=n;j++)
		if(a[i][j]!=NoEdge)
			sum++;
		return sum;
}
template<class T>
int AdjacencyWdigraph<T>::InDegree(int i) const
{
	if(i<1||i>n)
		throw BadInput();
	int sum=0;
	for(int j=1;j<=n;j++)
		if(a[j][i]!=NoEdge)
			sum++;
		return sum;
}
template<class T>
void AdjacencyWdigraph<T>::Output() const
{
	//Output the adjacency matrix.
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			cout<<a[i][j]<<" ";
		cout<<endl;
	}
}
template<class T>
class EdgeNode{
	friend ostream&operator<<(ostream&,EdgeNode<T>);

	friend AdjacencyWgraph<T>;
	friend void main(void);
public:
	operator T () const {return weight;}
public:
	T weight;
	int u,v;
};
//用邻接矩阵实现赋权无向图
template<class T>
class AdjacencyWgraph:public AdjacencyWdigraph<T>
{
	public:
		AdjacencyWgraph(int Vertices=10,T noEdge=0):AdjacencyWdigraph<T>(Vertices,noEdge) {}
		AdjacencyWgraph<T> &Add(int i,int j,const T &w)
		{
			AdjacencyWdigraph<T>::Add(i,j,w);
			a[j][i]=w;
			return *this;
		}
		AdjacencyWgraph<T> &Delete(int i,int j)
		{
			AdjacencyWdigraph<T>::Delete(i,j);
			a[j][i]=NoEdge;
			return *this;
		}
		int Degree(int i) const { return OutDegree(i); }
		bool Prim(EdgeNode<T> *t);
};



template<class T>
bool AdjacencyWgraph<T>::Prim(EdgeNode<T> *t)
{
  int i,j,k,kk=0;
  T *lowcost = new T [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[i][1];
    closest[i]=1;
    s[i]=false;
    }
  for (i = 1; i < n; i++){
    T 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;
    t[kk].weight = lowcost[j];
    t[kk].u = j;
    t[kk++].v = closest[j];
    s[j]=true;
    for (k = 2; k <= n; k++)
      if ((a[k][j]<lowcost[k])&&(!s[k])){
        lowcost[k]=a[k][j];
        closest[k]=j;
        }
    }
  return (kk == n-1);
}


void main()
{
	if(in.fail()){
		cout<<"input.txt is not exist!";
		exit(1);}
	int n,m;
	in>>n>>m;
	int a,b,c;
	AdjacencyWgraph<int> G(n,100000);
	for(int i=0;i<=m-1;i++)
	{
		in>>a>>b>>c;
		G.Add(a,b,c);
	}
	EdgeNode<int> *t=new EdgeNode<int>[n-1];
	int max=0;
	if(G.Prim(t))
	{
	for(i=0;i<n-1;i++)
		if(t[i].weight>max)
			max=t[i].weight;
		out<<max;
	}
	else
		out<<"-1"<<endl;
}