Detail solution of secondary growth tree and related C++ solution method

The definition of a subminiature tree
Let G=(V,E,w) be a connected undirected graph and T be a minimum spanning tree of graph G. If I have another tree, T1, full
I don't have a tree here, T prime, omega omega. < So T1, T1 is a subminiature tree of graph G.

An algorithm for solving subminiature trees
Convention: the set of new spanning trees formed by a feasible exchange of T is called the adjacent set of tree T, denoted as N(T).
Theorem 3: let T be the minimum spanning tree of graph G. If T1 satisfies (T1)=min{(T1)=min{(T1) | T' ∈ N(T)}, then T1 is G
Every little thing grows into a tree.
Proof: if T1 is not a subminiature tree of G, then there must be another spanning tree T',T'=T such that
Omega (T) (T 'omega or less) < Omega omega one, and by the definition of T1 we know that T does not belong to N of T
E (T)/E (T) = {a1, a2
1,... , the at}, E (T)/E (T) = {b1, b2,... ,bt}, where t p 2. According to lemma 1, there is one
A permutation bi1, bi2,... Bit, so that T+aj-bij is still a spanning tree of G, and all belong to N(T), so that omega aj p omega (bij),
So omega (T') p omega (T+aj-bij) p omega (T1), so it's a contradiction. So T1 is a subminiature tree of graph G.
Through the above theorem, we have a basic idea to solve the problem of subminiature tree.
First, find the minimum spanning tree T of the graph. Time order (Vlog2V+E)
Then, find the weight of the neighborhood set of T and the minimum spanning tree, that is, the subminiature tree of FIG. G.
If it is just a simple enumeration, the complexity is high. First, the complexity of the two edges is O(VE), and then determine whether the exchange
The feasible complexity is O(V), then the total time complexity is O(V2E). The algorithm is blind. After a simple
It is not difficult to find out from the analysis that every edge that is not in the tree can always form a ring. Only by deleting an edge on the ring can a ring be formed
Ensure that the spanning tree remains after the exchange, and the greater the weight of the deleted edge, the smaller the weight sum of the newly obtained spanning tree. We can
So we can reduce the complexity to order VE. That is a big step forward, but not good enough.
A review of the last model, the minimum-constrained spanning tree, shows that we have faced a similar problem and finally adopted dynamic rules
This method avoids double calculation and greatly reduces the complexity. We can use similar ideas for this problem. The first
First, do a pre-processing to find the edge with the largest weight on the path between every two nodes in the tree, and then, the enumeration graph is not in
The edge of the tree, with the preprocessing we just did, we were able to take order one time to get the edge with the largest weight on the ring that was formed.
How do you pre-process it? Because this is a tree, there is no need for a sophisticated algorithm, just a simple BFS.
The time complexity required for preprocessing is O(V2).
Thus, the time complexity of this step is reduced to order V2.
In summary, the time complexity of sub-minor trees is O(V2).

practice
Topic:

      Title description:  
      The minimum spanning tree is well known, the secondary spanning tree is the weight of the tree formed in the graph and the second smallest tree, this value may be equal to the weight of the minimum spanning tree, your task is to design an algorithm to calculate the minimum spanning tree of the graph.  
      Input:  
      There are multiple sets of data. A positive integer t in the first row indicates that there are t sets of data.  
      The first row of each set of data has two integers n and m (2) < = n < =100), followed by m rows, three positive integers s, e, and w in each row, indicating that the weight of the two-way path from s to e is w.  
      Output:  
      Output secondary tree values if there is no output -1.  
      Sample input:  
      2  
      3 3  
      1 2 1  
      2, 3, 2  
      3 1 3  
      4 4  
      1 2 2  
      2, 3, 2  
      2, 3, 4,  
      4 1 2  
      Sample output:  
      4  
      6  

Ac code (comments written clearly) :

 #include <stdio.h> 
  #include <stdlib.h> 
  #include <string.h> 
   
  #define MAX 100000 
   
  int father[210];  //Check and set
  int visit[210]; //Record the subscripts of the edges used in the minimum spanning tree
  int windex; //Record the number of edges used in the minimum spanning tree
   
  typedef struct node { 
    int st, ed, w; 
  } node; 
   
   
  void preProcess() 
  { 
    int i, len = sizeof(father) / sizeof(father[0]); 
   
    for (i = 0; i < len; i ++) { 
      father[i] = i; 
    } 
   
  } 
   
   
  int cmp(const void *p, const void *q) 
  { 
    const node *a = p; 
    const node *b = q; 
   
    return a->w - b->w; 
  } 
   
   
  int findParent(int x) 
  { 
    int parent; 
   
    if (x == father[x]) { 
      return x; 
    } 
   
    parent = findParent(father[x]); 
    father[x] = parent; 
     
    return parent; 
  } 
   
   
  int minTree(node *points, int m, int n) 
  { 
    preProcess(); 
   
    int i, count, flag, pa, pb; 
   
    for (i = count = flag = windex = 0; i < m; i ++) { 
      pa = findParent(points[i].st); 
      pb = findParent(points[i].ed); 
       
      if (pa != pb) { 
        visit[windex ++] = i; 
        father[pa] = pb; 
        count ++; 
      } 
   
      if (count == n - 1) { 
        flag = 1; 
        break; 
      } 
    } 
   
    return flag; 
  } 
   
   
  int secMinTree(node *points, int m, int n) 
  { 
    int i, j, min, tmp, pa, pb, count, flag; 
   
    for (i = 0, min = MAX; i < windex; i ++) { 
      preProcess(); 
   
      //Find a small tree
      for (j = count = tmp = flag = 0; j < m; j ++) { 
        if (j != visit[i]) { 
          pa = findParent(points[j].st); 
          pb = findParent(points[j].ed); 
   
          if (pa != pb) { 
            count ++; 
            tmp += points[j].w; 
            father[pa] = pb; 
          } 
   
          if (count == n - 1) { 
            flag = 1; 
            break; 
          } 
        } 
      } 
   
      if (flag && tmp < min)  min = tmp; 
    } 
   
    min = (min == MAX) ? -1 : min; 
   
    return min;  
  } 
   
   
  int main(void) 
  { 
    int i, t, n, m, flag, min; 
    node *points; 
   
    scanf("%d", &t); 
   
    while (t --) { 
      scanf("%d %d", &n, &m); 
   
      points = (node *)malloc(sizeof(node) * m);  
   
      for (i = 0; i < m; i ++) { 
        scanf("%d %d %d", &points[i].st, &points[i].ed, &points[i].w); 
      } 
   
      qsort(points, m, sizeof(points[0]), cmp); 
       
      flag = minTree(points, m, n); 
   
      if (flag == 0) {  //Cannot generate a minimum spanning tree
        printf("-1n"); 
        continue; 
      } else { 
        min = secMinTree(points, m, n); 
        printf("%dn", min); 
      } 
   
   
      free(points); 
    } 
   
    return 0; 
  }