Menu
I have been given a task where, in an undirected graph consisting of N vertices, i.e; numbered from 1 to N , & M edges. Graph is described by two arrays, A & B, both length M,. A pair (A[K], B[K]), for K from 0 to M-1, describes edge among vertex A[K] & vertex B[K].
Task is to assign values from the range [1..N] to the vertices of the graph,giving 1 number to each of the vertices. Such that sum all over edges of the values at the edges endpoints is maximal.
For eg:
N =5, A=[2,2,1,3],B=[1,3,4,4], the graph has 4 edges: (2,1),(2,3),(1,4),(2,4). Inorder to obtain max sum of weights,we can assign following values to vertices : 3,5,2,4,1 (to vertices 1,2,3,4,5).
Thus sum of values at all edges 7+8+7+9=31:
edge(2,3) : 7 = 5 (vertex 2) + 2 (vertex 3)
edge(2,1) : 8 = 5 (vertex 2) + 2 (vertex 1)
edge(1,4) : 7 = 5 (vertex 1) + 2 (vertex 4)
edge(2,4) : 9 = 5 (vertex 2) + 2 (vertex 4)
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.
NOW, I need to write a function that, given a positive integer N and two arrays A, B of M positive integers, returns the maximum possible sum of values of the edges’ endpoints.
For instance :
1. Given N = 5, A = [2, 2, 1, 2], B = [1, 3, 4, 4], the function should return 31, as explained above.
Did not have much luck with this can anyone help me with the solution thanks in advance!