好赋权有向道路534tc.cpp

设计一个算法

//tc//
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
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>
class AdjacencyWDigraph
{
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);
	void Floyd(int **p);
	void Output()const;
private:
	T NoEdge;
	int n;
	int e;
	T **a;
};
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)
{
	if(i<1||j<1||i>n||j>n||i==j||a[i][j]!=NoEdge) return *this;
	a[i][j]=w;
	e++;
	return *this;
}
template<class T>
AdjacencyWDigraph<T>& AdjacencyWDigraph<T>::Delete(int i,int j)
{
	if(i<1||j<1||i>n||j>n||a[i][j]==NoEdge) return *this;
	a[i][j]=NoEdge;
	e--;
	return *this;
}
template<class T>
void AdjacencyWDigraph<T>::Floyd(int **p)
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(a[i][j]) p[i][j]=1;
			else p[i][j]=0;
		for (i=1;i<=n;i++)
			p[i][i]=1;
    for (int k=1;k<=n;k++)
       for (int i=1;i<=n;i++)
           for (int j=1;j<=n;j++)
		   {
			  if (p[i][j]) continue;
              if (p[i][k]&&p[k][j]) 
			  {
				  p[i][j]=1; 
				  continue;
			  }
           }
}
template<class T>
void AdjacencyWDigraph<T>::Output()const
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			cout<<a[i][j]<<"  ";
		cout<<endl;
	}
}
void main()
{
	if(in.fail()) 
	{
		cout<<"the input.txt is not exist!"<<endl;
		exit(1);
	}
	int n,m,i,j,k,w;
	int **p;
	in>>n>>m;
    Make2DArray(p,n+1,n+1);
	AdjacencyWDigraph<int> A(n);
    for(k=0;k<m;k++)
	{
		in>>i>>j>>w;
		A.Add(i,j,w);
	}
	A.Floyd(p);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			out<<p[i][j]<<' ';
		out<<endl;
	}
	Delete2DArray(p,n+1);
}