题目描述
对于给定的无向图G，设计一个优先队列式分支限界法，计算G的最小权顶点覆盖。
输入
输入数据的第1 行有2 个正整数n 和m（n<100，m<3000），表示给定的图G 有n 个顶点和m条边，顶点编号为1，2，…，n。第2 行有n个正整数表示n个顶点的权。接下来的m行中，每行有2 个正整数u,v，表示图G 的一条边(u,v)。
输出
将计算出的最小权顶点覆盖的顶点权之和以及最优解输出。第1 行是最小权顶点覆盖顶点权之和；第2 行是最优解xi ，1 ≤i≤n ，xi =0 表示顶点i不在最小权顶点覆盖中, xi =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
参考代码
暂无
解析
暂无
