问题描述:给定一个赋权无向图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在最小权顶点覆盖中.
A.1:1:1
B.1:0.5:0.33
C.2:1:0.66
D.不能确定
A.c[C]+g[G]+b[B]
B.r[R]+M[M]+b[B]
C.r[R]+g[G]+b[B]
D.r[R]+g[G]+y[Y]
在m维空间中任意给定n''+1个格点(各坐标均为整数的点,n≥2);求证:其中必定有两个格点P(X1,...,Xn),Q(y1,...,yn)使得点M(,...,也是一个格点.
A.R—Y和B—Y
B.R—Y和G.Y
C.B—Y和G—Y
D.R.BY和G—B
给定有限状态机M=(Q,S,R,f,g,q1).它的状态图如图8-18所示。
a)求状态q2的cabba的后继以及可接受状态序列。
b)求状态q3的Hbaaba的后继以及可接受状态序列。
c)验证f(f(q2,aba),aba)=f(q2,abaaba),g(f(q2,aba),aba)=g(q2,abaaba).
d)求M对于激励abaaba的响应.
c)构造一台与M相似的状态赋值机,并求它对于激励abaaba的响应。
A.RGB模式中,RGB表示红(R)、绿(G)、蓝(B)三个颜色
B.HSL模式中,HSL表示色调(H)、饱和度(S)、亮度(L)
C.RGB和HSL模式分别应用于不同领域,RGB用于显示领域,HSL用于印刷领域
D.HSL模式下,每种HSL成分都可使用从0到255的值
算法设计:对于给定的实验和仪器配置情况,找出净收益最大的实验计划.
数据输入:由文件input.txt提供输入数据.文件第1行有两个正整数m和n,m是实验数,n是仪器数.接下来的m行,每行是一个实验的有关数据.第一个数是赞助商同意支付该实验的费用,然后是该实验需要用到的若干仪器的编号.最后一行的n个数是配置每个仪器的费用.
结果输出:将最佳实验方案输出到文件output.txt.第1行是实验编号,第2行是仪器编号,最后一行是净收益.