jackamahed Posted August 25, 2021 Share Posted August 25, 2021 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 More sharing options...
jackamahed Posted August 25, 2021 Author Share Posted August 25, 2021 FInd the atached question .need solution in PHP or JS Link to comment Share on other sites More sharing options...
Barand Posted August 25, 2021 Share Posted August 25, 2021 Serious case of deja vu here. Link to comment Share on other sites More sharing options...
jackamahed Posted August 25, 2021 Author Share Posted August 25, 2021 @Barand Can you please tell in english Link to comment Share on other sites More sharing options...
Barand Posted August 25, 2021 Share Posted August 25, 2021 Deja vu - loosely translated - "we've been here before". Link to comment Share on other sites More sharing options...
jackamahed Posted August 25, 2021 Author Share Posted August 25, 2021 Can you post solution ,i am stuck at generating vertices order 3,5,2,4,1 Link to comment Share on other sites More sharing options...
Barand Posted August 25, 2021 Share Posted August 25, 2021 Guideline # 3 - read it. Link to comment Share on other sites More sharing options...
requinix Posted August 25, 2021 Share Posted August 25, 2021 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 More sharing options...
Recommended Posts