杭电OJ——1233 还是畅通工程(最小生成树有关问题)
杭电OJ——1233 还是畅通工程(最小生成树问题)
还是畅通工程
Problem Description
某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省*“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。
当N为0时,输入结束,该用例不被处理。
当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 5Huge input, scanf is recommended.HintHint
Source
浙大计算机研究生复试上机考试-2006年
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; }不懂的同学建议先了解一下克鲁斯卡尔算法!