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

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

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

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

Sample Input

31 2 11 3 22 3 441 2 11 3 41 4 12 3 32 4 23 4 50

Sample Output

35HintHint Huge input, scanf is recommended.

Source浙大计算机研究生复试上机考试-2006年
RecommendJGShining 就是一个最小生成树的问题，直接套用克鲁斯卡尔算法做即可！另外还有一点要注意，数组尽量开大点，我一连交了几次都是提示数组越界，测试数据之多可见一般！下面发代码！

//典型的最小生成树问题//克鲁斯克拉算法#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条边，初值为1j=1;//E中边的下标，初值为0while(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的改为sn1vset[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;elseg.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;}

不懂的同学建议先了解一下克鲁斯卡尔算法！