好套汇问题509arbi.cpp

设计一个算法

#include<iostream>
#include<fstream>
using namespace std;
ifstream in ("input.txt");
ofstream out ("output.txt");

char **name;
int n,m,s;
template<class T>
class AdjacencyWDigraph
{
	friend void main(void);
	public:
		AdjacencyWDigraph (int Vertices=10,T noEdge=0);
		int Edges() const{return e;}
		int Vertices() const{return n;}
		AdjacencyWDigraph<T> & Add(int i,int j,const T& w);
		void Output();
		void Input(int n,ifstream& in);
		int Floyd();
	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;
	a=new T*[n+1];
	for(int i=0;i<=n;i++)
		a[i]=new T [n+1];
	for(i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			a[i][j]=NoEdge;
}

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)
		throw;
	a[i][j]=w;
	e++;
	return *this;
}




template<class T>
void AdjacencyWDigraph<T>::Output() 
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			cout<<a[i][j]<<' ';
	
		cout<<endl;
	}
}
template<class T>
int  AdjacencyWDigraph<T>::Floyd()
{

	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
				T t1=a[i][k];
				T t2=a[k][j];
				T t3=a[i][j];
				if(t1!=NoEdge && t2!=NoEdge && (t3==NoEdge || t1*t2>t3))
				{
					a[i][j]=t1*t2;
				}
			}
			for(int i=1;i<=m;i++)
			{
				if(a[i][i]>1) 
				{
					s=1;
					return s;
				}
				else
				{
					s=0;
					return s;
				}
			}
			return s;
				
}
template <class  T>
void AdjacencyWDigraph<T>::Input(int n,ifstream& in)
{
		char *x=new char;
		char *z=new char;
		double y;
		for(int i=1;i<=m;i++)
		{
			in>>x;
			int s=exchange(x);
			in>>y;
			in>>z;
			int t=exchange(z);
			a[s][t]=y;
		}
}
int  exchange(char *x)
{
   for(int r=1;r<=n;r++)
	   if(strcmp(x,name[r])==0)
		   break;
   return r;
}

void main()
{
		ifstream in ("input.txt");
	if(in.fail()) 
	{
		cout<<"the input.txt is not exit";
		exit(1);
	}
	ofstream out ("output.txt");

	for(int r=1;;r++)
	{
		in>>n;
		int i,j;
		if(n==0) break;
		name=new char *[n+1];
		for(i=0;i<=n;i++)
			name[i]=new char[1000]; //定义一个存放国家的数组
		for(j=1;j<=n;j++)
			in>>name[j];

		in>>m;
		int l;
		AdjacencyWDigraph<double>  G(n,0);
		G.Input(m,in);
	//	G.Output();
		//out<<endl;
		l=G.Floyd();


	//	G.Output();
	//	cout<<endl<<endl;



		if(l==1) 
			out<<"Case"<<' '<<r<<' '<<"Yes"<<endl;
		else
			out<<"Case"<<' '<<r<<' '<<"No"<<endl;
		for(i=0;i<=n;i++)
			delete[] name[i];
		delete[] name;
	}

}