Jump to content

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.


Recommended Posts

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,2],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 functionthat, 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. 

 

 

Your school does not allow people to ask for help on the internet. How do I know that? Because you aren't the first to ask.

It's especially bad that you're asking for a solution instead of help to find the solution, so I'm not going to redact the images you've posted.

Guest
This topic is now closed to further replies.
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.