如果结果不匹配，请 
更多“如果顶点的总数为n，则Prim算法总共要选择n-1条边来构成…”相关的问题
合成数(composite number)法，是消除图算法岐义性的一种通用方法。首先，在顶点的标识之间约定某一次序。比如，顶点标识为整数或字符时，可直接以整数或字符为序;对于字符串等标识，不妨按字典序排列。于是，若边(v，u)权重为w，则对应的合成数取作向量：(w，min(v，u)，max(v，u))。如此，任何两条边总能明确地依照字典序比较出大小。
试在6.11.5节Prim算法和6.12.2节Dijkstra算法中引入这一方法，以消除其中的歧义性。
a)若套用Kruskal或Prim算法构造EMST(G)，各需多少时间？
b)试设计一个算法，在o(nlogn)时间内构造出EMST(G);
c)试证明你的算法已是最优的(亦即，在坏情况下，任何此类算法都需要o(nlogn)时间)。
试设计一个算法,利用T公司提供的m个补丁程序,将原软件修复成一个没有错误的软件,并使修复后的软件耗时最少.
算法设计:对于给定的n个错误和m个补丁程序,找到总耗时最少的软件修复方案.
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和m,n表示错误总数,m表示补丁总数(1≤n≤20,1≤m≤100).接下来m行给出了m个补丁的信息.每行包括一个正整数,表示运行补丁程序i所需时间以及2个长度为n的字符串,中间用个空格符隔开.在第1个字符串中,如果第k个字符bk为“+”,则表示第k个错误属于B1[i],若为“-”,则表示第k个错误属于B2[i],若为“0”,则第k个错误既不属于B1[i]也不属于B2[i],即软件中是否包含第k个错误并不影响补丁i的可用性.在第2个字符串中,如果第k个字符bk为“+”,则表示第k个错误属于F1[i],若为“-”,则表示第k个错误属于F2[i],若为“0”,则第k个错误既不属于F1[i]也不属于F2[i],即软件中是否包含第k个错误不会因使用补丁i而改变.
结果输出:将总耗时数输出到文件output.txt.如果问题无解,则输出0.
问题描述:给定有向图G=(V,E).设P是G的一个简单路(顶点不相交)的集合.如果V中每个顶点恰好在P的条路上,则称P是G的一个路径覆盖.P中路径可以从V的任何一个项点开始,长度也是任意的,特别地,可以为0.G的最小路径覆盖是G的所含路径条数最少的路径覆盖.
设计一个有效算法求一个有向无环图G的最小路径覆盖.
[设V={1,2,...,n},如下构造网络G1=(V1,E1):
每条边的容量均为1.求网络G1的(x0,y0)最大流.]
算法设计:对于给定的有向无环图G,找出G的一个最小路径覆盖.
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和m.n是给定有向无环图G的顶点数,m是G的边数.接下来的m行,每行有2个正整数i和j,表示一条有向边(i,j).
结果输出:将最小路径覆盖输出到文件output.txt.从第1行开始,每行输出一条路径.文件的最后一行是最少路径数.
在多叉堆(d-heap)中，每个节点至多可拥有d≥3个孩子，且其优先级不低于任一孩子。
a)试证明，多叉堆decrease()接口的效率可改进至O(logdn);(当然，delMax()接口的效率因此会降至O(d-logn))。
b)试证明，若取d=e/n+2，则基于d叉堆实现的Prim算法的时间复杂度可降至O(e·logdn);
c)这种改进策略是否也适用于Dijkstra算法？
设G是一个有n个顶点的有向图,从顶点i发出的边的最小费用记为min(i).
(1)证明图G的所有前缀为x[1,i]的旅行售货员问路的费用至少为:
式中,a(u,v)是边(u,v)的费用.
(2)利用上述结论设计一个高效的上界函数,重写旅行售货员问题的回溯法,并与主教材中的算法进行比较.
