`
bcyy
  • 浏览: 1809334 次
文章分类
社区版块
存档分类
最新评论

杭电OJ——1233 还是畅通工程(最小生成树问题)

 
阅读更多

还是畅通工程

Problem Description
某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。

Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。
当N为0时,输入结束,该用例不被处理。

Output
对每个测试用例,在1行里输出最小的公路总长度。

Sample Input
3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0

Sample Output
3 5
Hint
Hint
Huge input, scanf is recommended.

Source

Recommend
JGShining
就是一个最小生成树的问题,直接套用克鲁斯卡尔算法做即可!另外还有一点要注意,数组尽量开大点,我一连交了几次都是提示数组越界,测试数据之多可见一般!下面发代码!
//典型的最小生成树问题

//克鲁斯克拉算法
#include<iostream>
using namespace std;
const int MAXV=200;
const int MAXE=9999;
const int INF=99999999999999;

typedef struct
{
	int u;//边的起始顶点
	int v;//边的终止顶点
	int w;//边的权值
}EdgeType;

typedef struct
{
	int edge[MAXV][MAXV];
	int n,e;//分别为顶点数和边数
}MGraph;


void InsertSort(EdgeType E[],int n)
{
	int i,j;
	EdgeType temp;
	for(i=2;i<=n;i++)
	{
		temp=E[i];
		j=i-1;//从右至左在有序区E[0……i-1]中找E[i]的插入位置
		while(j>=1 && temp.w<E[j].w)//向前面搜寻,一旦看见比temp.w大的
		{
			E[j+1]=E[j];//将w大于E[i].w的记录后移,注意一点,前面i-1个已经有序
			j--;
		}
		E[j+1]=temp;//在j+1处插入E[i]
	}

}

int Kruskal(MGraph g)
{
	EdgeType E[MAXE];
	int i,j,m1,m2,sn1,sn2,k,sum;
	int vset[MAXV];
	//k=0;
	k=1;
	sum=0;
	for(i=1;i<=g.n;i++)//将各边存入E[0……g.e-1]数组当中
		for(j=1;j<=g.n;j++)
			if(g.edge[i][j]!=0 && g.edge[i][j]!=INF)
			{
				E[k].u=i;
				E[k].v=j;
				E[k].w=g.edge[i][j];
				k++;
			}
			//cout<<"k="<<k<<endl;
			InsertSort(E,g.e);//对E数组按照权值从小到大排列
			//for(i=1;i<=g.e;i++)
				//cout<<E[i].w<<endl;
			//cout<<endl;

			for(i=1;i<=g.n;i++)
				vset[i]=i;//初始化辅助数组
			k=1;//k表示当前构造的最小生成树的第k条边,初值为1


			j=1;//E中边的下标,初值为0
			while(k<g.n)//生成的边数小于n
			{
				m1=E[j].u;
				m2=E[j].v;//取得一条边的头尾顶点

				sn1=vset[m1];
				sn2=vset[m2];//分别得到两个顶点所属的集合编号

				if(sn1!=sn2)//两顶点属于不同的集合,则该边是最小生成树的一条边
				{
					k++;
					sum=sum+E[j].w;
					for(i=1;i<=g.n;i++)//两个集合统一编号
						if(vset[i]==sn2)//集合编号为sn2的改为sn1
							vset[i]=sn1;
				}
				j++;//下一条边
			}
			return sum;
}

int main()
{
	int num,i,j,m,n,temp;
	MGraph g; 
	while(cin>>num && num!=0)
	{
		g.n=num;
		g.e=num*(num-1)/2;
		for(i=1;i<=g.n;i++)
			for(j=1;j<=g.n;j++)
				if(i==j) g.edge[i][j]=0;
				else
				g.edge[i][j]=INF;
		
		for(i=1;i<=g.e;i++)
		{
			scanf("%d%d%d",&m,&n,&temp);
			g.edge[m][n]=temp;
		}
      cout<<Kruskal(g)<<endl;
	}
	return 0;
}
不懂的同学建议先了解一下克鲁斯卡尔算法!

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics