#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();
}