center.cpp

对于给定的赋权有向图G

#include<iostream>
#include<fstream>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
template<class T>
class AdjacencyWGraph
{
  public:
	  AdjacencyWGraph(int vertices=10,T noEdge=0);
	  ~AdjacencyWGraph(){Delete2DArray(a,n+1);}
	  bool Exist(int i,int j) const;
	  int Edges()const {return e;}
	 int Vertices()const{return n;}
	  AdjacencyWGraph<T>& Add (int i,int j,const T&w);
	  AdjacencyWGraph<T>& Delete(int i,int j);
   int OutDegree(int i)const;
   int InDegree(int i) const;
   void Output() const;
   void Make2DArray(T **&x,int rows,int cols);
   void Delete2DArray(T**&x,int rows);
void  Floyd(T**c,int **path);
  private:
	  T NoEdge;
	  int n;
	  int e;
	  T **a;
	  };
template<class T>
void AdjacencyWGraph<T>::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 AdjacencyWGraph<T>:: Delete2DArray(T**&x,int rows)
{
	for(int i=0;i<rows;i++)
        delete[]x[i];
	delete []x;
	x=0;
}
template<class T>
AdjacencyWGraph<T>::AdjacencyWGraph(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 AdjacencyWGraph<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>
AdjacencyWGraph<T>&AdjacencyWGraph<T>::Add (int i,int j,const T&w)
{
	a[i][j]=w;
	e++;
	return *this;
}
template<class T>
AdjacencyWGraph<T>&AdjacencyWGraph<T>::Delete(int i,int j)
{
  a[i][j]=NoEdge;
  e--;
  return *this;
}
template<class T>
 int  AdjacencyWGraph<T>:: OutDegree(int i)const
{
 int sum=0;
for(int j=1;j<=n;j++)
  if(a[i][j]!=NoEdge) sum++;
    return sum;
}
template<class T>
int AdjacencyWGraph<T>:: InDegree(int i)const
{
int sum=0;
for(int j=1;j<=n;j++)
  if(a[j][i]!=NoEdge)  sum++;
  return sum;
}
template<class T>
void AdjacencyWGraph<T>::Output() const
{

	for(int i=1;i<=n;i++){
  for(int j=1;j<=n;j++)
out<<a[i][j]<<' ';
	out<<endl;
	}
}
template<class T> 
void AdjacencyWGraph<T>::Floyd(T **c,int **path)
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
		c[i][j]=a[i][j];
		path[i][j]=0;
		}
for( i=1;i<=n;i++)
     c[i][i]=0;
 for(int k=1;k<=n;k++)
	 for(int i=1;i<=n;i++)
		 for(int j=1;j<=n;j++)
		 {
		 T t1=c[i][k];
		 T t2=c[k][j];
		 T t3=c[i][j];
		 if(t1!=NoEdge&&t2!=NoEdge&&(t3==NoEdge||t1+t2<t3))
		 {
		 c[i][j]=t1+t2;
		 path[i][j]=k;}
		 }
}
int main()
{
	int n,m,temp,symbol;
	in>>n>>m;
AdjacencyWGraph<int> matrix(n);
for(int i=1;i<=m;i++)
{ 
	int a,b,w;
   in>>a>>b>>w;
   matrix.Add(a,b,w);
    
}
int **array=new int*[n+1];
int **sign=new int *[n+1];
for(int j=1;j<=n;j++)
{
  array[j]=new int[n+1];
  sign[j]=new int[n+1];
}

matrix.Floyd(array,sign);
int *max=new int [n+1];
for(j=1;j<=n;j++)
{ 
	max[j]=array[1][j];
	 for(i=1;i<=n;i++)
   
	 if(array[i][j]>max[j])
	 max[j]=array[i][j];
}
symbol=i=1;
while(!max[i])
{
i++;
symbol++;}
temp=max[i];
for(j=i+1;j<=n;j++)
  if(max[j]<temp)
  {
	  temp=max[j];
  symbol=j;}
  out<<temp<<endl<<symbol<<endl;
  return 1;
}