minimumcostspanningtree.cpp

北大2485的简单题目。用了最小生成树

#include<iostream>
#include<stdio.h>
using namespace std;

#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 500//最大顶点个数
typedef unsigned int VertexType;   //
typedef unsigned int VRType;       //



typedef struct{
	
	VertexType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];       //邻接矩阵
	int vexnum,arcnum;         //图的当前顶点数和弧数
}MGraph;

struct {
	VertexType adjvex;       //储存衣服在U中的顶点
	VRType lowcost;          //权值
}closedge[MAX_VERTEX_NUM];


int minimum(MGraph &G)
{
	 int k;
	 for(k=0;k<G.vexnum;k++)
		 if(closedge[k].lowcost!=0)break;
	
	for(int i=k;i<G.vexnum;i++)
	{
		
		if(closedge[k].lowcost>closedge[i].lowcost&&closedge[i].lowcost!=0)
			k=i;
	}
	
	return k;
}

void MiniSpanTree_PRIM(MGraph &G,unsigned int save[])
{
	int k=0,l=0;                       //定位k值
	int j;
	
	for(j=0;j<G.vexnum;++j)                //辅助数组初始化
		if(j!=k) 
		{
			closedge[j].adjvex=k;
			closedge[j].lowcost=G.arcs[k][j];
		}           
	
	closedge[k].lowcost=0;    //初始，U={u}
	
	/*
	for(j=0;j<G.vexnum;++j)
		cout<<closedge[j].adjvex<<" "<<closedge[j].lowcost<<endl;
*/

	for(int i=1;i<G.vexnum;++i)              //选择其余G.vexnum-1个顶点
	{
		k= minimum(G);           //求出T的下一个结点：第K个结点
		
		 //cout<<closedge[k].lowcost<<endl;//输出生成树的边
		save[l]=closedge[k].lowcost;
		l++;
		closedge[k].lowcost=0;                  //第k项点并入U集

		
/*
	for(j=0;j<G.vexnum;++j)
		cout<<closedge[j].adjvex<<" "<<closedge[j].lowcost<<endl;
*/



	for(j=0;j<G.vexnum;++j)
	{
			if(G.arcs[k][j]<closedge[j].lowcost)       //新顶点并入U后重新选择小边
			{

				closedge[j].adjvex=k;
				closedge[j].lowcost=G.arcs[k][j];
			}
	}
	
	}
}


void exchange(unsigned int &a,unsigned int &b)
{
	unsigned int temp;
	temp=a;
	a=b;
	b=temp;
}

int Sort(unsigned int k[],int vex)
{
	unsigned int flag;
	flag =k[0];
	for(int i=1;i<vex-1;i++)
	if(flag<k[i])
			exchange(flag,k[i]);
	return flag;
}

void CreatMGraph(MGraph &G,int vex)
{
	int i,j;
	for(i=0;i<vex;i++)
		for(j=0;j<vex;j++)
			cin>>G.arcs[i][j];
	G.vexnum=vex;
	G.arcnum=vex;
	
}
int main()
{
	int i;
	
	cin>>i;
	getchar();
	for(int j=0;j<i;j++)
	{
		int vex;
		int answer;
		unsigned int save[MAX_VERTEX_NUM]={0};
		cin>>vex;
		MGraph G;
		CreatMGraph(G,vex);

		
	
	
		

		MiniSpanTree_PRIM(G,save);
		answer=Sort(save,vex);
		cout<<answer<<endl;
	}
		//getchar();
		//getchar();
		return 0;
}