FastPrep

Description

Solutions

Submission

Assign Values

🔥 FULLTIME

You are given an undirected graph consisting of N vertices, numbered from 1 to N, and M edges. The graph is described by two arrays, A and B, both of length M. A pair (A[K], B[K]), for K from 0 to M-1, describes an edge between vertex A[K] and vertex B[K].

Your task is to assign all values from the range [1..N] to the vertices of the graph, giving one number to each of the vertices. Do it in such a way that the sum over all edges of the values at the edges' endpoints is maximal.

Notice that the value assigned to vertex 5 did not have any effect on the final result as it is not an endpoint of any edge.

Example 1:

Input:  N = 5, A = [2, 1, 2], B = [1, 3, 4, 4]
Output: 31 
Explanation:
In order to obtain the maximum sum of weights, you can assign the following values to the vertices: 3, 5, 2, 4, 1 (to vertices 1, 2, 3, 4, 5 respectively). This way we obtain the sum of values at all edges' endpoints equal to 7 + 8 + 7 + 9 = 31.
      
edge (2, 3): 7 = 5 (vertex 2) + 2 (vertex 3)
    
edge (2, 1): 8 = 5 (vertex 2) + 3 (vertex 1)
     
edge (1, 4): 7 = 3 (vertex 1) + 4 (vertex 4)
    
edge (2, 4): 9 = 5 (vertex 2) + 4 (vertex 4)

Constraints:

N/A