# Problem D

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 $N-1$ and the graph will not contain multi-edges or self-loop.

## Input

The first line of standard input contains two integers: $1 \leq N \leq 4000$ and $0 \leq E \leq 600000$ representing the number of vertices and edges respectively. The second line of standard input contains $N$ integers. The $i^{th}$ integer represents the vertex weight for the $i^{th}$ 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 $x \neq y$.

## 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 $N-1$ 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=(Val - Opt)/(Naive - Opt)$. (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.02^{x}$. 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 |