C++ program to find the maximum sum of a minimally connected graph

Suppose we have a minimally connected graph. This means that deleting any edge will disconnect the graph. The graph has n vertices and the edges are given in the array "edges". We also get an array "vertexValues" containing n integer values.

Now, we do the following -

• We write a positive integer at each vertex and then try to calculate a fraction.

• There is an edge connecting two vertices, and we put the smaller value of the two vertices on the edge.

• We calculate the score by adding all edge values.

We have to find the maximum value which can be achieved by placing the value on the vertex. We have to print the maximum total value and the value to be written to the vertex.

So if the input is something like n = 6, then Edges = {{1, 2}, {2, 3} , {2, 4}, {4, 5}, {3, 6}} , vertexValues ​​= {1, 2, 3, 4, 5, 6}, then the output will be 15, 3 1 2 4 5 6, because we can put the values ​​from 0 in the given way 3 1 2 4 5 6 to the vertex n – 1.

To solve this problem we will follow the following steps-

N := 100
Define arrays seq and res of size N.
Define an array tp of size N.
ans := 0
Define a function dfs(), this will take p, q,
   res[p] := seq[c]
   if p is not equal to 0, then:
      ans := ans + seq[c]
   (decrease c by 1)
   for each value x in tp[p], do:
      if x is not equal to q, then:
         dfs(x, p)
for initialize i := 0, when i + 1 < n, update (increase i by 1), do:
   tmp := first value of edges[i]- 1
   temp := second value of edges[i] - 1
   insert temp at the end of tp[tmp]
   insert tmp at the end of tp[temp]
for initialize i := 0, when i < n, update (increase i by 1), do:
   seq[i] := vertexValues[i]
c := n - 1
sort the array seq
dfs(0, 0)
print(ans)
for initialize i := n - 1, when i >= 0, update (decrease i by 1), do:
   print(res[i])

Example

Let us see the following implementation for better understanding-

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
#define N 100
int seq[N], res[N];
vector<int> tp[N];
int ans = 0, c;

void dfs(int p, int q) {
   res[p] = seq[c];
   if(p != 0)
      ans += seq[c];
   c--;
   for(auto x : tp[p]) {
      if(x != q)
         dfs(x, p);
   }
}
void solve(int n, vector<pair<int,int>> edges, int vertexValues[]){
   for(int i = 0; i + 1 < n; i++) {
      int tmp = edges[i].first - 1;
      int temp = edges[i].second - 1;
      tp[tmp].push_back(temp);
      tp[temp].push_back(tmp);
   }
   for(int i = 0; i < n; i++)
      seq[i] = vertexValues[i];
   c = n - 1;
   sort(seq, seq + n);
   dfs(0, 0);
   cout << ans << endl;
   for(int i = n - 1; i >= 0; i--)
      cout << res[i] << " ";
   cout << endl;
}
int main() {
   int n = 6;
   vector<pair<int,int>> edges = {{1, 2}, {2, 3}, {2, 4}, {4, 5},{3, 6}};
   int vertexValues[] = {1, 2, 3, 4, 5, 6};
   solve(n, edges, vertexValues);
   return 0;
}

Input

6, {{1, 2}, {2, 3}, {2, 4}, {4, 5}, {3, 6}}, {1, 2, 3, 4, 5, 6}

Output

15
3 1 2 4 5 6

The above is the detailed content of C++ program to find the maximum sum of a minimally connected graph. For more information, please follow other related articles on the PHP Chinese website!