The Minimum Weighted Vertex Cover (MWVC) problem is to find the vertex cover with
the minimum sum of weights of a particular given graph.
Your program should take as input a single MWVC instance. It
will be run several times, once for every test case. The time
limit is per test case.
For simplicity, the graph will contain vertices and undirected edges. The vertices
will be labelled from
to and the graph
will not contain multi-edges or self-loop.
Input
The first line of standard input contains two integers:
and
representing the number of vertices and edges respectively. The
second line of standard input contains integers. The integer represents the vertex
weight for the
vertex. All vertex weights are positive and will be not more
than 1 000 000. The following lines each contain a pair of
vertex numbers, and
. This denotes that
there is an undirected edge connecting vertices and . It is guaranteed that
.
Output
On the first line, output the total sum of vertex weights in
the vertex cover. On the second line, output up to vertices on a single line. These
vertices should not
contain duplicate values and should form a vertex cover. More
specifically, all vertex numbers must be within and and there should not be two of
the same vertex number in the line.
Score
Let be the length
of an optimal minimum weighted vertex cover, be the sum of vertex weights of
the vertex cover found by your solution, and be the sum of vertex weights
found by the algorithm below.
Define . (In the special case that , define if , and if .)
The score on a test case is . Thus, if your vertex cover
is optimal, you will get 1 point on this test case. If your
score is halfway between and , you get roughly points. The total score of your
submission is the sum of your score over all test cases. There
will be a total of
test cases. Thus, an implementation of the algorithm below
should give a score of at least (it will get 0.02 points on most
test cases, and 1.0 points on some easy cases where it manages
to find an optimal solution).
The algorithm giving the value is the as follows:
SimpleWVC(vertices, edges)
for every edge (u, v) in edges
if weight[u] < weight[v]
used[u] = True
else if weight[u] > weight[v]
used[v] = True
else if u < v
used[u] = True
else
used[v] = True
initialize vertex_cover to an empty list
for i = 0 to n-1
if used[i]
append i to vertex_cover
return vertex_cover
Sample Input 1 |
Sample Output 1 |
8 9
1 1 999 1 1 1 999 100
0 1
1 2
1 4
2 3
2 5
3 6
4 5
5 6
6 7
|
103
1 3 5 7
|