分支限界法 最小权顶点覆盖问题

【文件属性】：
文件名称：分支限界法 最小权顶点覆盖问题
文件大小：363KB
文件格式：RAR
更新时间：2014-05-11 12:46:38
最小权顶点覆盖问题 ★问题描述：给定一个赋权无向图G=(V,E),每个顶点v∈V都有一个权值w(v)。如果U∈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不在最小权顶点覆盖中。

【文件预览】：
五、分支限界法
----6-2.opt(48KB)
----6-2.ncb(41KB)
----Debug()
--------vc60.pdb(116KB)
--------6-2.exe(536KB)
--------6-2.obj(251KB)
--------6-2.pdb(1.05MB)
----MinHeap.h(2KB)
----6-2.dsp(3KB)
----6-2.cpp(4KB)
----6-2.dsw(514B)
----6-2.plg(733B)