2004011270_p1.cpp

利用图的存储、表示以及最短路径相关算法解决销售网络扩张问题。

#include <iostream.h>
#include <fstream.h>
#include <iomanip.h>
const int MaxVertexNum=100;
const int MaxEdgeNum=50;
const int MaxValue=50;
typedef int vexlist[MaxVertexNum];
typedef int adjmatrix[MaxVertexNum][MaxVertexNum];//存储邻接矩阵
int n,e;
struct edgenode{  
	int adjvex;
	int weight;
	edgenode *next;
};
struct edge {  //定义边集数组的元素类型
	int fromvex;  //边的起点域
	int endvex;  //边的终点域
	int weight;		//边的权值域
};
typedef edge edgeset[MaxEdgeNum];  //定义edgeset为边集数组类型
typedef edgenode *adjlist[MaxVertexNum];
ifstream tfile;  //输入流
	

void Create1(adjmatrix GA,int n,int e,ifstream tfile)//建立邻接数组
{
	int i,j,k,w;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++){		//初始化邻接数组
			if(i==j)
				GA[i][j]=0;
			else
				GA[i][j]=MaxValue;
		}
		for(k=1;k<=e;k++){		//建立邻接数组
			tfile>>i>>j>>w;
		GA[i][j]=GA[j][i]=w;
		}
}

void Create2(adjmatrix GA,int n,int e,int g[],int m,ifstream tfile)
{		//找到A B各自的城市后建立邻接数组
	int i,j,k,w,flag1=0,flag2=0;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++) {
			if(i==j)
				GA[i][j]=0;
			else
				GA[i][j]=MaxValue;		//初始化
		}

		for(k=1;k<=e;k++) {
			tfile>>i>>j>>w;
			GA[i][j]=GA[j][i]=w;
		}
		for(i=0;i<n;i++)
		GA[m][i]=GA[i][m]=MaxValue+1;		
		for(j=0;j<n;j++)
		for(i=1;i<n/2;i++)
			GA[j][g[i]]=GA[g[i]][j]=MaxValue+1;	//如果有另一个网中的城市权值置为MaxValue;

		
}
void findmin(adjmatrix GA,int dist[],int h[],int i,int n,ofstream ttt)
{		//利用狄克斯特拉算法求图GA中从顶点i到其余每个顶点间的最短距离，存在dist数组中
	int j,k,w,m;
	int *s=new int [n];	//定义作为集合使用的动态数组s；
	for(j=0;j<n;j++) {
		if(j==i)
			s[j]=1;
		else
			s[j]=0;
		dist[j]=GA[i][j];
	}
	for (k=1;k<=n-2;k++)	//共进行n-2次循环，每次求出从原点i到终点m得最短长度
	{
		w=MaxValue; m=i;
		for(j=0;j<n;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<n;j++)
				if(s[j]==0&&dist[m]+GA[m][j]<dist[j]) {
					dist[j]=dist[m]+GA[m][j];
				}
	}
for(j=1;j<n-1;j++)
h[j]=j;
	int M,K,J,I,d;
K=1;M=n-2;
while(K<M)	//对dist进行排序，并对保存城市序号的数组h进行相应的排序
{
	J=M-1;
	M=1;
	for(I=K;I<=J;I++)
		if(dist[I]>dist[I+1])
		{d=dist[I];dist[I]=dist[I+1];dist[I+1]=d;
		d=h[I];h[I]=h[I+1];h[I+1]=d;M=I;}
		J=K+1;K=1;
		for(I=M;I>=J;I--)
			if(dist[I-1]>dist[I])
			{d=dist[I];dist[I]=dist[I-1];dist[I-1]=d;
		d=h[I];h[I]=h[I-1];h[I-1]=d;K=I;}
}
ttt<<"Ci"; 
	for(j=1;j<n-1;j++)		//将排好序的城市序号及相应的权值读入文件中
	ttt<<setw(8)<<h[j]; ttt<<endl;
	if(i==0)
		ttt<<"to Ca"; 
	else 
		ttt<<"to Cb";
	for(j=1;j<n-1;j++)
	ttt<<setw(8)<<dist[j]; ttt<<endl;
}



void Prim(adjmatrix GA,edgeset CT,int g[],int n,ofstream ttt)
{	//利用普里姆算法从顶点出发求出用邻接矩阵GA表示的图的最小生成树，存于边集数组CT中
	int i,j,k,min,t,m,w;
	for(i=0;i<n-1;i++) {
		CT[i].fromvex=0;
		CT[i].endvex=i+1;
		CT[i].weight=GA[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;
			}
			if(CT[m].weight==MaxValue)
				break;
			edge 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=GA[j][t];
				if(w<CT[i].weight) {
					CT[i].weight=w;
					CT[i].fromvex=j;
				}
			}
	}

	for(i=0;i<n-1;i++)
		
	{
		if(CT[i].weight<MaxValue)	//输出边集
			ttt<<"("<<CT[i].fromvex<<","<<CT[i].endvex<<")"<<CT[i].weight<<"  ";
		if(CT[i].weight==MaxValue) 
			ttt<<CT[i].endvex<< "     "; //输出孤立点
	}
		ttt<<endl;
}
	
void main(int argc, char *argv[])
{
	ifstream tfile(argv[1]);
	ofstream ttt(argv[2]);
	adjmatrix GA,GB,GC;		//定义三个邻接数组分别存原图及A,B的邻接矩阵
	edgeset CT1,CT2;  //定义两个边集数组分别存两个网的最小生成树
	int a=1,b=0,c=0,d=0,f=0,q;
	int dist1[100];		//存A到各点的权值
	int dist2[100];		//存B到各点的权值
	int h1[100];	//存各城市序号	
	int h2[100];
	int g1[100];	//存A网的城市序号
	int g2[100];	//存B网的城市序号
	int *visit=new int[n];	//定义一个数组，标记该城市是够被占领，占领则置零

	if(tfile)
	{
		tfile>>n>>e;
		n=n+2;
		Create1(GA,n,e,tfile);	//构造保存图的邻接矩阵
	}
	
	tfile.close();
	findmin(GA,dist1,h1,0,n,ttt);	//找到A到各点的最短距离
	ttt<<endl;
	findmin(GA,dist2,h2,n-1,n,ttt);	//找到B到各点的最短距离
	ttt<<endl;

	dist1[0]=0;dist2[0]=0;
	dist1[n-1]=dist2[n-1]=MaxValue;
	h1[n-1]=h2[n-1]=MaxValue;
	for(int j=1;j<n-1;j++)
	{
		g1[j]=MaxValue;g2[j]=MaxValue;	//初始化g1,g2
	}
		for(j=1;j<n-1;j++)
		visit[j]=1;

	for( j=1;j<n/2;j++)
	{
		q=j;
		while(visit[h1[q]]==0&&q<n-2)	//如果该城市已被占领，则访问下一个城市
			q++;

		d=q;
		if(q=n-2&&visit[h1[q]]==0)
			g1[a]=MaxValue;
		q=j;
		
		while(visit[h2[q]]==0&&q<n-2)
			q++;

		f=q;
		if(q=n-2&&visit[h2[q]]==0)
			g2[a]=MaxValue;
		q=j;
		
		if(h1[d]==h2[f]&&dist1[d]<=dist2[f])	//如果找到同一个城市但
		{								//A的距离短或相等，则给A,让B往下一个找
			visit[h1[d]]=0;
			g1[a]=h1[d];
			f=f+1;
			while(visit[h2[f]]==0&&f<n-2)
				f++;
			g2[a]=h2[f];
			visit[h2[f]]=0;
		}
		
	else if(h1[d]==h2[f]&&dist1[d]>dist2[f])	//如果找到同一个城市但B
		{		//的距离较近，则给B,让A往下一个找
			visit[h1[d]]=0;
			g2[a]=h2[f];
			d++;
			while(visit[h1[d]]==0&&d<n-2)
				d++;
			g1[a]=h1[d];
			visit[h1[d]]=0;

		}
	else if(h1[d]!=h2[f])
		{		//如果找到的不是同一个城市，则分别给A和B
			g1[a]=h1[d];g2[a]=h2[f];
			visit[h1[d]]=0;visit[h2[f]]=0;
		}
		a++;
	}

	ttt<<"A cities:";	//输出A的城市
	for(j=1;j<=n/2;j++)
		{
		if(g1[j]!=MaxValue)
		{
			ttt<<setw(8)<<g1[j];
			b++;
		}
		else ;
	}
		ttt<<endl;
	ttt<<"B cities:";	//输出B的城市
	for(j=1;j<=n/2;j++)
	{
		if(g2[j]!=MaxValue)
		{
			ttt<<setw(8)<<g2[j];
			c++;
		}
		else ;
	}


		ttt<<endl;
		ttt<<endl;
		ttt<<"A net:";
	tfile.open(argv[1]);
	if(tfile)
		{
		tfile>>b>>e;

		Create2(GB,n,e,g2,n-1,tfile);	//构造保存A网的临接数组
	}

Prim(GB,CT1,g1,n,ttt);	//利用普里姆算法求出A网的最小生成树

tfile.close();
ttt<<"B net:";
tfile.open(argv[1]);
	if(tfile)
		{
		tfile>>c>>e;

		Create2(GC,n,e,g1,0,tfile);	//构造保存B网的临接数组
	}

Prim(GC,CT2,g2,n,ttt);	//利用普里姆算法求出B网的最小生成树
ttt.close();
}