还是畅通工程
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
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;
}
不懂的同学建议先了解一下克鲁斯卡尔算法!
分享到:
相关推荐
杭电oj1000题解题报告
杭电OJ题目分类的叙述,可以方便去学习去做。
这是杭电oj入门100题的题号,通过这100题可以掌握基本输入输出操作,及基本算法
杭电OJ 2028代码 the rosolve of the hdu 2028
本资源主要提供了杭电oj题目分类和自测状况两大类 可实现随机选题等功能.
杭电OJ(1000-1099) AC 代码
杭电OJ部分威士忌的代码 杭电OJ部分威士忌的代码杭电OJ部分威士忌的代码
杭电oj 1047习题
杭电oj上的一些疑问,适用于初学者,可以解答一些疑问 都是一些水题
杭州电子科技大学 oj离线版
杭电oj分类
杭电oj的离线版以及题目分类的文档 更加一目了然 方便选择适合的题目做 适合暂时上不了网的用于练习
这是HDUOJ上面的140道题目的答案,其中大部分都是简单题,有些太简单的就没有收集进去,代码为C/C++,全都AC了的,其中有些有具体的说明是怎么做的,例如博弈论那些
课程资源 杭电OJ1000-1099答案 ,仅供参考...
这是杭电OJ上某些题的解题报告,后续还有上传很多!
基于Laravel 5.0的OJ题解网站 , 目前涵盖安科OJ,南阳OJ,杭电OJ ,北大OJ,浙大OJ.zip
杭电离线oj(2010版),方便不能上网的朋友用,比别的版本增加了很多题!
杭电oj1048答案,c++代码,适合初学者,思路简单