intmain.cpp

06年全国研究生数学建模竞赛之邮车调度问题的答案程序。可能根据题目给出的地图

#include"graph.h"
#include<iomanip>
#include<fstream>

float zhiju(int *bef,int m)
{
	int i;
	float c=0.0;
    for(i=0;i<m;i++)
		if(bef[i]>0&&bef[i]<74)c=c+1;
	return c;
}

void paixu(int *bef,int m)
{
	int k,min;
	int i,j;
	for(i=0;i<m-1;i++)
	{
		k=i;
		for(j=i+1;j<m;j++)
			if(bef[j]<bef[k])
			k=j;
		if(i!=k)
		{
			min=bef[i];
			bef[i]=bef[k];
			bef[k]=min;
		}
	}
}




int main()
{
	int v,i,j,k,t;
	int befsome[50];
	char choice,choice1;
	float mindis,time,zj;
	GRaph gra;
	ElemType str;
	int indegree[maxnode];//入函数后再将其分配空间
	int p[maxnode][maxnode],d[maxnode],sign[maxnode][maxnode];
	while(1)
	{
		cout<<setfill('*')<<setw(20)<<"主菜单"<<setw(20)<<'*'<<endl;
	    cout<<"1:读取文件建立有权无向图UDN的领接表和邻接矩阵。"<<endl;	
		cout<<"2:显示图的领接表结构。"<<endl;
		cout<<"3:显示UDN图的prim最小生成树各条边。"<<endl;
		cout<<"4:求一源点到其他顶点的最短路径(DIJ)。"<<endl;
		cout<<"5:求图的floyd矩阵"<<endl;
		cout<<"6:求任意两点的最短距离(使用前先求floyd矩阵)。"<<endl;
		cout<<"7:求某一点到其他点的最佳线路，即不完整最佳销售员回路(使用前先求floyd矩阵)。"<<endl;
	    cout<<"0:结束程序。"<<endl;
		cout<<setw(50)<<'*'<<endl;
		cin>>choice;
		while(choice<'0'||choice>'10')
		{
			cout<<"输入错误，请重新输入：";
			cin>>choice;
		}
		switch(choice)
		{
			case '1':
				gra.getdata();
				cout<<"有权无向图的领接表和邻接矩阵建立成功。"<<endl;
				break;
			case '2':
				cout<<"图的邻接表结构如下:"<<endl;
				gra.ShowUDN();
				break;
			case '3':
				cout<<"输入想从哪个顶点(直接输入顶点名字而不是序号)开始生成prim树:";
				cin>>str;
				cout<<"prim最小生成树的各边如下："<<endl;
				gra.MiniSpanTree_PRIM(str);
				break;
			case'4':
				cout<<"输入想从哪个县局(名字)开始:";
				cin>>str;
				gra.ShortestPath_DIJ(str,p,d,sign);
				break;
			case'5':
				gra.Floyd();
				cout<<"求解floyd矩阵成功"<<endl;
				break;
			case '6':
				cout<<"输入两个点的序号。";
				cin>>i>>j;
				if(gra.A[i][j]>=infinity){cout<<"两点没有直达路径。"<<endl;break;}
				else
				{
				cout<<"最短距离为：";
				cout<<gra.A[i][j]<<endl;
				cout<<"路径为：";
				gra.Showpah1(i,j);
				}
				break;
			case'7':
    while(1)
	{
		cout<<setfill('*')<<setw(20)<<"菜单"<<setw(20)<<'*'<<endl;
	    cout<<"1:区车(即从区局D点出发)。"<<endl;	
		cout<<"2:县车(即从县局出发)。"<<endl;
	    cout<<"0:返回主菜单。"<<endl;
		cout<<setw(50)<<'*'<<endl;
		cin>>choice1;
		while(choice1<'0'||choice1>'2')
		{
			cout<<"输入错误，请重新输入：";
			cin>>choice1;
		}
		switch(choice1)
		{
			case '1':
				cout<<"输入原点(在邻接矩阵中的序号)";
				cin>>real0;
				cout<<"输入（邮车）要经过的顶点数m：";
				cin>>m;
				t=m;
				sign1[0]=real0;
				cout<<"请依次输入m个要经过的顶点在图的邻接表中的序号（注意是序号不是名字）："<<endl;
				for(i=0;i<t;i++)
					cin>>befsome[i];
               paixu(befsome,m);
                mindis=gra.travel(real0,befsome,m);
				zj=zhiju(befsome,m);
				time=0;
				time+=zj*5/60.0;
				time+=(m-zj)*10/60.0;
				time+=mindis/65;
			    cout<<"最短距离为："<<mindis<<",成本为"<<3*mindis<<"元。"<<endl;
				cout<<"所用时间(包括在每个点卸邮件)为："<<time<<"小时。"<<endl;
				cout<<"途径的点为:"<<endl;
	            t--;
				while(t>0)
				{
					k=inbef(sign1[t+1],befsome);
					exchange(befsome[k],befsome[t]);
					gra.travel(sign1[t+1],befsome,t);
					t--; 
				};
				for(i=0;i<m;i++)
				{
					cout<<gra.graph[sign1[i]].vertexname<<"->";
                    gra.Showpah(sign1[i],sign1[i+1]);
				}
				cout<<gra.graph[sign1[m]].vertexname<<"->";
				gra.Showpah(sign1[m],real0);
				cout<<gra.graph[real0].vertexname<<endl;
				break;

			case '2':
				cout<<"输入原点(在邻接矩阵中的序号)";
				cin>>real0;
				cout<<"输入（邮车）要经过的顶点数m：";
				cin>>m;
				t=m;
				sign1[0]=real0;
				cout<<"请依次输入m个要经过的顶点在图的邻接表中的序号（注意是序号不是名字）："<<endl;
				for(i=0;i<t;i++)
					cin>>befsome[i];
                paixu(befsome,m);
                mindis=gra.travel(real0,befsome,m);
				zj=zhiju(befsome,m);
				time=0;
				time+=zj*5.0/60.0;
				time+=(m-zj)*10.0/60.0;
				time+=mindis/30;
				cout<<"最短距离为："<<mindis<<",成本为"<<3*mindis<<"元。"<<endl;
				cout<<"所用时间(包括在每个点卸邮件)为："<<time<<"小时。"<<endl;
				cout<<"途径的点为:"<<endl;
	            t--;
				while(t>0)
				{
					k=inbef(sign1[t+1],befsome);
					exchange(befsome[k],befsome[t]);
					gra.travel(sign1[t+1],befsome,t);
					t--; 
				};
				for(i=0;i<m;i++)
				{
					cout<<gra.graph[sign1[i]].vertexname<<"->";
                    gra.Showpah(sign1[i],sign1[i+1]);
				}
				cout<<gra.graph[sign1[m]].vertexname<<"->";
				gra.Showpah(sign1[m],real0);
				cout<<gra.graph[real0].vertexname<<endl;
				break;
			case '0':
			goto A;
		}	
	
	}
A:	break;
				
			case '0':return 0;
		}
	}
}