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.


jackamahed

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. 

 

 

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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.