题目内容
（请给出正确答案）
[主观题]
问题描述:给定一个赋权无向图G=（V,E),每个顶点都有权值w（v).如果,且对任意（u,V)∈E有u∈U或v∈U,
问题描述:给定一个赋权无向图G=(V,E),每个顶点
都有权值w(v).如果
,且对任意(u,V)∈E有u∈U或v∈U,就称U为图G的一个顶点覆盖.G的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖.
算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,...,n.第2行有n个正整数表示n个顶点的权.接下来的m行中,每行有2个正整数u和v,表示图G的一条边(u,v).
结果输出:将计算的最小权顶点覆盖的顶点权值和以及最优解输出到文件output.txt.文件的第1行是最小权顶点覆盖顶点权之和;第2行是最优解xi(1≤i≤n),xi=0表示顶点i不在最小权顶点覆盖中,xi=1表示顶点i在最小权顶点覆盖中.
查看答案
如果结果不匹配，请 联系老师 获取答案
更多“问题描述:给定一个赋权无向图G=（V,E),每个顶点都有权值…”相关的问题
每个文件占用磁盘上的1个磁道.这n个文件的检索概率分别是
且
磁头从当前磁道移到被检信息磁道所需的时间可用这两个磁道之间的径向距离来度量.如果文件fi存放在第i(1≤i≤n)道上,则检索这n个文件的期望时间是
.式中,d(i,j)是第i道与第j道之间的径向距离|i-j|.
处.居民们希望在城市中至少选择一个,但不超过k个居民点建立服务机构.在每个居民点xi处,服务需求量为wi≥0.在该居民点设置服务机构的费用为ci≥0.假设居民点xi到距其最近的服务机构的距离为di,则居民点x的服务费用为
建立k个服务机构的总费用为A+B.A是在k个居民点设置服务机构的费用的总和;B是n个居民点服务费用的总和.
,计算在直线L上最多设置k处服务机构的最小总费用.
