Hide

Problem C
Minimum Weighted Vertex Cover

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 N vertices and E undirected edges. The vertices will be labelled from 0 to N1 and the graph will not contain multi-edges or self-loop.

Input

The first line of standard input contains two integers: 1N4000 and 0E600000 representing the number of vertices and edges respectively. The second line of standard input contains N integers. The ith integer represents the vertex weight for the ith vertex. All vertex weights are positive and will be not more than 1 000 000. The following E lines each contain a pair of vertex numbers, x and y. This denotes that there is an undirected edge connecting vertices x and y. It is guaranteed that xy.

Output

On the first line, output the total sum of vertex weights in the vertex cover. On the second line, output up to N vertices on a single line. These N vertices should not contain duplicate values and should form a vertex cover. More specifically, all vertex numbers must be within 0 and N1 and there should not be two of the same vertex number in the line.

Score

Let Opt be the length of an optimal minimum weighted vertex cover, Val be the sum of vertex weights of the vertex cover found by your solution, and Naive be the sum of vertex weights found by the algorithm below.

Define x=(ValOpt)/(NaiveOpt). (In the special case that Naive=Opt, define x=0 if Val=Opt, and x=inf if Val>Opt.)

The score on a test case is 0.02x. Thus, if your vertex cover is optimal, you will get 1 point on this test case. If your score is halfway between Naive and Opt, you get roughly 0.14 points. The total score of your submission is the sum of your score over all test cases. There will be a total of 40 test cases. Thus, an implementation of the algorithm below should give a score of at least 0.8 (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 Naive 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
Hide

Please log in to submit a solution to this problem

Log in