搜索
最小生成树MSTminimum-costspannirngtree2015/1/28最小生成树问题：假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？该问题等价于：构造网的一棵最小生成树，即：在e条带权的边中选取n-1条边（不构成回路）使“权值之和”为最小1.普里姆算法prim();2.克鲁斯卡尔算法Kruskal();prim()算法任意一个顶点u作为生成树的根之后往生成树上添加新的顶点v在添加的顶点w和已经在生成树上的顶点v之间必定存在一条边，并且该边的权值在所有连通顶点u和v之间的边中取值最小之后继续往生成树上添加顶点，直至生成树上含有n-1个顶点为止。abcdegf195141827168213127prim()算法动态图形演示：aedcbgf148531621所得生成树权值和=14+8+3+5+16+21=67样例题目：描述最近，小Hi很喜欢玩的一款游戏模拟城市开放出了新Mod，在这个Mod中，玩家可以拥有不止一个城市了！但是，问题也接踵而来——小Hi现在手上拥有N座城市，且已知这N座城市中任意两座城市之间建造道路所需要的费用，小Hi希望知道，最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达（假设有A、B、C三座城市，只需要在AB之间和BC之间建造道路，那么AC之间也是可以通过这两条道路连通的）。样例题目：输入：每个测试点（输入文件）有且仅有一组测试数据。在一组测试数据中：第1行为1个整数N，表示小Hi拥有的城市数量。接下来的N行，为一个N*N的矩阵A，描述任意两座城市之间建造道路所需要的费用，其中第i行第j个数为Aij，表示第i座城市和第j座城市之间建造道路所需要的费用。对于100%的数据，满足N=10^3，对于任意i，满足Aii=0，对于任意i,j满足Aij=Aji,0Aij10^4.输出：对于每组测试数据，输出1个整数Ans，表示为了使任意两座城市都可以通过所建造的道路互相到达至少需要的建造费用。样例题目：样例输入501005696339211821005015994213145169631599097802789392421397800523611821451278952360样例输出：4178程序代码：代码程序代码：代码程序代码：codekruskal算法问题的出发点：为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。算法思路：1.建立一个边集（该边集按照权值成“递增”顺序）（一般用结构体）2.从边集开始找边加到树上。当第一条边加到树上后，此时树上有两个节点，此时的权值和就是这条边。接着添加第二条边，这是就要判断这条边的加入会不会和之前的已经加入到树上的那些边组成回路呢？如果组成回路，则说明该边不可以加到该生成树上否则可以。就这样一直往生成树上加边，直到生成树上有n-1条边了。退出循环，输出权值总和。abcdegf195141827168213127aedcbgf148531621Kruskal算法动态图形演示：7121819样例题目：描述随着小Hi拥有城市数目的增加，在之间所使用的Prim算法已经无法继续使用了——但是幸运的是，经过计算机的分析，小Hi已经筛选出了一些比较适合建造道路的路线，这个数量并没有特别的大。所以问题变成了——小Hi现在手上拥有N座城市，且已知其中一些城市间建造道路的费用，小Hi希望知道，最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达（假设有A、B、C三座城市，只需要在AB之间和BC之间建造道路，那么AC之间也是可以通过这两条道路连通的）样例题目：输入每个测试点（输入文件）有且仅有一组测试数据。在一组测试数据中：第1行为2个整数N、M，表示小Hi拥有的城市数量和小Hi筛选出路线的条数。接下来的M行，每行描述一条路线，其中第i行为3个整数N1_i,N2_i,V_i，分别表示这条路线的两个端点和在这条路线上建造道路的费用。对于100%的数据，满足N=10^5,M=10^6，于任意i满足1=N1_i,N2_i=N,N1_i≠N2_i,1=V_i=10^3.对于100%的数据，满足一定存在一种方案，使得任意两座城市都可以互相到达。输出对于每组测试数据，输出1个整数Ans，表示为了使任意两座城市都可以通过所建造的道路互相到达至少需要的建造费用。样例题目：程序代码：程序代码：算法比较：算法名：普里姆算法库鲁斯卡尔算法时间复杂度：O（n^2）O（e*loge）适用：稠密图稀疏图放映完毕