英国零售电商网站开发,微网站 建设,做个个人网站多少钱,网页设计代码tdDescription 某省调查乡村交通状况#xff0c;得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通#xff08;但不一定有直接的公路相连#xff0c;只要能间接通过公路可达即可#xff09;#xff0c;并要求铺设… 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 35 解题思路典型的最小生成树的问题利用krusal算法代码简洁效率高。但是在构建图的时候尽量不要用邻接矩阵因为邻接矩阵既浪费空间有耗时间采用邻接表更好正解#includecstdio
#includealgorithm
typedef struct
{int from;int to;int value;
}Node,*node;
int Find(int *father,int x)
{if(x!father[x])father[x]Find(father,father[x]);return father[x];
}
void Union(int *father,int from,int to)
{int aFind(father,from);int bFind(father,to);father[a]b;
}
bool cmp(const Node a,const Node b)
{return a.valueb.value;//从小到大排序
}
using namespace std;
int main()
{int N,i0;while(~scanf(%d,N),N){Node mp[N*N1];int father[N1];for(i0;iN;i)father[i]i;for(i0;iN*(N-1)/2 ;i)scanf(%d%d%d,mp[i].from,mp[i].to,mp[i].value);sort(mp,mpN*(N-1)/2,cmp);int sum0;for(i0;iN*(N-1)/2;i){if(Find(father,mp[i].from)!Find(father,mp[i].to)){Union(father,mp[i].from,mp[i].to);summp[i].value;}//printf(%d %d %d\n,mp[i].from,mp[i].to,mp[i].value);}printf(%d\n,sum);}return 0;
}
开始写时的错误代码因为”动态“数组的边界数开的范围不正确#includealgorithm//Runtime Error(ACCESS_VIOLATION)#includecstdioint Find(int * helper,int a)//传递了数组的地址 { if(a!helper[a]) helper[a]Find(helper,helper[a]); return helper[a];}//并查集FIND void Union(int * helper,int a,int b)//传递了数组的地址 { int xFind(helper,a);//找a的父节点 int yFind(helper,b);//b的父节点 helper[y]x;//合并 }//并查集UNION typedef struct M{ int a; int b; int v;}Node;//存储图的边(u,v)以及对应的值 bool cmp(const Node x,const Node y){ return x.vy.v;}//sort排序对值进行降序排序 using namespace std;int main(void){ int N; while(scanf(%d,N)!EOFN) { Node vex[N];//存储(u,v)关系(错误 int helper[N1];//新建并查集 for(int i0;iN1;i) helper[i]i;//并查集初始化 int T0; while(T!N*(N-1)/2) scanf(%d%d%d,vex[T].a,vex[T].b,vex[T].v); sort(vex,vexN,cmp); int sum0; for(int i0;iN;i)//K...算法 { if(Find(helper,vex[i].a)!Find(helper,vex[i].b)) { Union(helper,vex[i].a,vex[i].b); sumvex[i].v;//记录树的总值 } } printf(%d\n,sum); } return 0;}
