2076_AL081最小权顶点覆盖问题

给定一个赋权无向图G=(V,E)，每个顶点v∈V都有一个权值w(v)。如果U V，且对任意(u,v)∈E 有u∈U 或v∈U，就称U为图G的一个顶点覆盖。G 的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖。

对于给定的无向图G，设计一个优先队列式分支限界法，计算G的最小权顶点覆盖。

输入第一行有两个正整数n和m，表示给定的图G有n个顶点和m条边，顶点编号为1，2，…，n。

第二行有n个正整数表示n个顶点的权。接下来的m行中，每行有两个正整数 u, v，表示图G 的一条边(u,v)。

输出最小权顶点覆盖的顶点权之和以及最优解。第一行是最小权顶点覆盖顶点权之和；第二行是最优解x_i ，1 ≤ i ≤ n ，x_i=0 表示顶点i不在最小权顶点覆盖中，x_i=1 表示顶点i在最小权顶点覆盖中。

7 7
1 100 1 1 1 100 10
1 6
2 4
2 5
3 6
4 5
4 6
6 7

13
1 0 1 1 0 0 1

要求：采用 优先队列式分支限界法