Preparing NOJ

无相图问题

1000ms 65536K

Description:

 给定一个赋权无向图G=(V,E),每个顶点vV都有一个权值w(v)。如果UÍV,且对任意(u,v)E uU vU,就称U 为图G 的一个顶点覆盖。G 的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖。对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖。

Input:

1 行有2 个正整数n m,表示给定的图G n 个顶点和m条边,顶点编号为12,…,n。第2 行有n个正整数表示n个顶点的权。接下来的m行中,每行有2 个正整数u,v,表示图G 的一条边(u,v)

Output:

程序运行结束时,将计算出的最小权顶点覆盖的顶点权之和以及最优解输出。第1行是最小权顶点覆盖顶点权之和;文件第2行是最优解   x i ,1 £ i £ n   x i =0 表示顶点i不在最小权顶点覆盖中, x i =1 表示顶点i在最小权顶点覆盖中

Sample Input:

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

Sample Output:

13
1 0 1 1 0 0 1

Note:

 

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1315

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet