sale_web.cpp

实现一个销售网络扩张后A、B 分店所在城市分布查询系统

//*****************************************************
//*程 序 名: 销售网络扩张问题	                      *
//*作    者: 陈子冲 2004011066 无45		              *
//*编制时间: 2006年4月30日                            *
//*主要功能: 提供扩张后A、B 分店所在城市分布          *
//*****************************************************

//*******INCLUDES**************************************************
#include<iostream.h>
#include<fstream.h>
#include<iomanip.h>
#define MaxValue 65535
//定义边集数组的元素类型
struct edge{
			int fromvex;
			int endvex;
			int weight;
			};
//*******FUNCTIONS*************************************************
//用Dijkstra算法解决最短路径问题（用邻接矩阵GA表示的图）
void Dijkstra(int** GA,int *dist,int i,int VertexNum)
{
	int j,k,w,m;
	int *s=new int[VertexNum];
	for(j=0;j<VertexNum;j++) dist[j]=MaxValue;
	for(j=0;j<VertexNum;j++){
		if(j==i)
			s[j]=1;
		else 
			s[j]=0;
		dist[j]=GA[i][j];
	}

	for(k=1;k<=VertexNum-2;k++)
	{
		w=MaxValue;m=i;
		for(j=0;j<VertexNum;j++)
			if(s[j]==0&&dist[j]<w){
				w=dist[j];
				m=j;
			}
		if(m!=i)
			s[m]=1;
		else
			break;
		for(j=0;j<VertexNum;j++)
			if(s[j]==0&&dist[m]+GA[m][j]<dist[j]){
				dist[j]=dist[m]+GA[m][j];
			}

	}
	delete []s;

}
//从Dijkstra算法得到的dist[]数组中找到最小值（除去被标记的元素以外）
int findmin(int *dist,int *flag,int VertexNum)
{
	int i=0,j,m;
	while(flag[i]!=0) i++;
	m=dist[i];
	for(j=0;j<VertexNum;j++)
	{
		if(flag[j]==1) continue;
		if(m>dist[j]) m=dist[j],i=j;
	}
	flag[i]=1;
	return i;

}
//用Prim算法得到邻接矩阵GB表示图的最小生成树
void Prim(int **GB,edge *CT,int n)
{
	int i,j,k,min,t,m,w;
	edge temp;
	for(i=0;i<n-1;i++)
	{
		CT[i].fromvex=0;
		CT[i].endvex=i+1;
		CT[i].weight=GB[0][i+1];
	}
	for(k=1;k<n;k++)
	{
		min=MaxValue;
		m=k-1;
		for(j=k-1;j<n-1;j++)
			if(CT[j].weight<min){
				min=CT[j].weight;
				m=j;
			}
		temp=CT[k-1];
		CT[k-1]=CT[m];
		CT[m]=temp;
		j=CT[k-1].endvex;
		for(i=k;i<n-1;i++){
			t=CT[i].endvex;
			w=GB[j][t];
			if(w<CT[i].weight){
				CT[i].weight=w;
				CT[i].fromvex=j;
			}
		}
	}
}


//主函数
void main(int argc, char *argv[])
{
	int **GA,**GB,*dist,*flag,*tempA,*tempB,*temp,i,j,k,VertexNum,ta,tb;
	edge *CT;
	ifstream fin(argv[1]);	//创建输入文件
	ofstream fout(argv[2]);	//创建输出文件
	//输入顶点数到VertexNum
	fin>>VertexNum;VertexNum+=2;
	fin>>i;
	//输入图的信息到GA中（存为无向图）
	GA=new int* [VertexNum];
	for(i=0;i<VertexNum;i++)
		GA[i]=new int [VertexNum];
	for(i=0;i<VertexNum;i++)
		for(j=0;j<VertexNum;j++)
			GA[i][j]=MaxValue;
	while(fin.eof()!=1)
	{
		fin>>i>>j>>k;
		GA[i][j]=k;
		GA[j][i]=k;
	}
	//初始化用于求两个网络最小生成树的邻接矩阵GB
	GB=new int* [VertexNum/2];
	for(i=0;i<VertexNum/2;i++)
		GB[i]=new int [VertexNum/2];
	for(i=0;i<VertexNum/2;i++)
		for(j=0;j<VertexNum/2;j++)
			GB[i][j]=MaxValue;
	//初始化数组
	dist=new int[VertexNum];
	flag=new int[VertexNum];
	tempA=new int[VertexNum];
	tempB=new int[VertexNum];
	temp=new int[VertexNum];
	CT=new edge[VertexNum/2];
	
	fin.close();
	//求A公司所在城市到预扩张的N 个城市的最短距离
	Dijkstra(GA,dist,0,VertexNum);
	for(i=0;i<VertexNum;i++)
		flag[i]=0;
	fout<<"Ci:";
	//对dist[]排序、同时按照最短距离的大小从小到大输出
	for(i=0;i<VertexNum-2;i++)
	{
		tempA[i]=findmin(dist,flag,VertexNum);
		if(tempA[i]==0||tempA[i]==VertexNum-1) i--;
		else fout<<setw(8)<<tempA[i];
	}
	fout<<endl<<"to Ca:";
	for(i=0;i<VertexNum-2;i++)
		fout<<setw(8)<<dist[tempA[i]];
	fout<<endl<<endl;
	//求B公司所在城市到预扩张的N 个城市的最短距离
	Dijkstra(GA,dist,VertexNum-1,VertexNum);
	for(i=0;i<VertexNum;i++)
		flag[i]=0;
	fout<<"Ci:";
	for(i=0;i<VertexNum-2;i++)
	{
		tempB[i]=findmin(dist,flag,VertexNum);
		if(tempB[i]==0||tempB[i]==VertexNum-1) i--;
		else fout<<setw(8)<<tempB[i];
	}
	fout<<endl<<"to Cb:";
	for(i=0;i<VertexNum-2;i++)
		fout<<setw(8)<<dist[tempB[i]];
	fout<<endl<<endl;
	//按照A、B每月扩张一次的方式来模拟生成结果
	fout<<"A cities:";
	for(i=0;i<VertexNum;i++)
		flag[i]=0;
	ta=0,tb=0;
	for(i=0;i<VertexNum/2-1;i++)
	{
		while(flag[tempA[ta]]==1) ta++;
		while(flag[tempB[tb]]==1) tb++;
		if(tempA[ta]==tempB[tb])
		{
			if(dist[tempA[ta]]<=dist[tempB[tb]])
			{
				temp[i+1]=tempA[ta];
				flag[tempA[ta]]=1;
				while(flag[tempB[tb]]==1) tb++;
				temp[i+VertexNum/2+1]=tempB[tb];
			}
			else
			{
				temp[i+VertexNum/2+1]=tempB[tb];
				flag[tempB[tb]]=1;
				while(flag[tempA[ta]]==1) ta++;
				temp[i+1]=tempA[ta];
			}
		}
		else
		{
			temp[i+1]=tempA[ta];
			temp[i+VertexNum/2+1]=tempB[tb];
		}
		flag[tempA[ta]]=1;
		flag[tempB[tb]]=1;
		fout<<setw(8)<<tempA[ta];
	
	}
	fout<<endl<<endl<<"B cities:";
	for(i=0;i<VertexNum/2-1;i++)
		fout<<setw(8)<<temp[i+VertexNum/2+1];
	fout<<endl<<endl;
	//用Prim算法找到属于A的城市的最小生成树
	temp[0]=0;temp[VertexNum/2]=VertexNum-1;
	for(i=0;i<VertexNum/2;i++)	//把属于A的城市放到GB中
		for(j=0;j<VertexNum/2;j++)
			GB[i][j]=GA[temp[i]][temp[j]];
	Prim(GB,CT,VertexNum/2);	//调用Prim算法
	fout<<"A net:";
	i=0;
	while(CT[i].weight<MaxValue&&i<VertexNum/2-1)	//输出
	{
		fout<<" ("<<temp[CT[i].fromvex]<<","<<temp[CT[i].endvex]<<")"<<CT[i].weight;
		i++;
	}
	while(i<VertexNum/2-1)	//输出
	{
		fout<<" "<<temp[CT[i].endvex];
		i++;
	}
	//找到属于B的城市的最小生成树
	for(i=0;i<VertexNum/2;i++)
		for(j=0;j<VertexNum/2;j++)
			GB[i][j]=GA[temp[i+VertexNum/2]][temp[j+VertexNum/2]];
	Prim(GB,CT,VertexNum/2);
	fout<<endl<<endl<<"B net:";
	i=0;
	while(CT[i].weight<MaxValue&&i<VertexNum/2-1)	//输出
	{
		fout<<" ("<<temp[CT[i].fromvex+VertexNum/2]<<","<<temp[CT[i].endvex+VertexNum/2]<<")"<<CT[i].weight;
		i++;
	}
	while(i<VertexNum/2-1)	//输出
	{
		fout<<" "<<temp[CT[i].endvex+VertexNum/2];
		i++;
	}
	//关闭输出好的文件
	fout.close();


}