销售员.cpp

用c++写一个售货员问题。这是高级算法中除了红黑树中最难的一个了。是研究生课程中的的程序实现

#include "iostream.h"
#include "stdio.h"
int M(int a[5][5])
{
	   int p,m,n,l,k;
	   k=0;
	   for(m=0;m<5;m++)
	   {		  
		  p=a[m][0];
		  for(l=0;l<5;l++)
		     if(a[m][l]<p)
			   p=a[m][l];
		  if(p==1000)	     
		  {
			 p=0;
		  }
		  k+=p;
	 	  for(n=0;n<5;n++)
	         if((a[m][n]!=1000)&&(p!=1000))
				 a[m][n]-=p;
	   }
	   for(n=0;n<5;n++)
	   {  
		   p=a[0][n];
	       for(l=0;l<5;l++)
			  if(a[l][n]<p)
			     p=a[l][n];
	       if(p==1000)
			   p=0;
		   k+=p;
           for(m=0;m<5;m++)
			   if((a[m][n]!=1000)&&(p!=1000))
				   a[m][n]-=p;
	   }
	   return(k);
}
void N(int b[5][5],int p,int q)
{   
   	int k,n;
    k=b[p][q];
	for(n=0;n<5;n++)
	   {
		   b[p][n]=1000;
	       b[n][q]=1000;
	   }
	b[p][q]=k;
	b[q][0]=1000;

}
void 
main()
{

    int A[5][5],B[5][5],C[5][5],D[5][5],s[5],road[5],r[5],k,l,i,j,cost,m,p,t,q;
	cout<<"输入五个节点的带权连通图(无穷用1000表示):\n";
	for(i=0;i<5;i++)
	{
		cout<<"\n";
		for(j=0;j<5;j++)
		{
			cin>>A[i][j];
			D[i][j]=A[i][j];//D[]为A[]的原距阵
		}
		cout<<"\n";
	}
    cost=M(A);
	r[0]=cost;
	for(i=0;i<5;i++)
	   for(j=0;j<5;j++)
	    	C[i][j]=A[i][j];//A[]的规约距阵
    s[0]=1;//是否已经到达过的标志树组
	road[0]=0;//路径树组
	for(i=1;i<5;i++)
       s[i]=0;
	m=0;
    for(j=1;j<5;j++)
	{
       	t=10000;

		for(i=1;i<5;i++)
		{
			if(s[i]==0)
			{
				N(A,m,i);
			    l=M(A);
                if(l<t)
				{
					t=l;
					k=i;
					for(p=0;p<5;p++)
						for(q=0;q<5;q++)
							B[p][q]=A[p][q];//每次规约的距阵
						
				}
			}
            for(p=0;p<5;p++)
			   for(q=0;q<5;q++)
				  A[p][q]=C[p][q];
		
		}
     	s[k]=1;
		m=k;
		cost+=t;
		r[j]=t;
		road[j]=k;
		for(p=0;p<5;p++)
		{
		  for(q=0;q<5;q++)
		  {
			  A[p][q]=B[p][q];
              C[p][q]=B[p][q];
			
				 
		  }
		}
    cout<<"\n";

    }
	cout<<"路径为:";
	for(i=0;i<5;i++)
		cout<<road[i]<<"  ";
	cout<<"\n";
	cout<<"每个节点对应的花费为:";
    for(i=0;i<5;i++)
	cout<<r[i]<<"  ";
	cout<<"\n";
	
	cout<<"遍历每个节点后回到原点的花费为:"<<cost<<"\n";

}