Programme C++ pour trouver la somme maximale d'un graphe minimalement connecté-C++-php.cn

Programme C++ pour trouver la somme maximale d'un graphe minimalement connecté

WBOY

Libérer： 2023-09-13 13:53:13

avant

1182 Les gens l'ont consulté

Programme C++ pour trouver la somme maximale dun graphe minimalement connecté

Supposons que nous ayons un graphe minimalement connecté. Cela signifie que la suppression d’une arête déconnectera le graphique. Le graphe a n sommets et les arêtes sont données dans le tableau "edges". Nous obtenons également un tableau "vertexValues" contenant n valeurs entières.

Maintenant, nous procédons comme suit -

Nous écrivons un entier positif à chaque sommet puis essayons de calculer une fraction.
Il y a une arête reliant deux sommets et nous mettons la plus petite valeur des deux sommets sur l'arête.
Nous calculons le score en additionnant toutes les valeurs de bord.

Nous devons trouver la valeur maximale qui peut être atteinte en plaçant la valeur sur le sommet. Nous devons imprimer la valeur totale maximale et la valeur à écrire sur le sommet.

Donc, si l'entrée est quelque chose comme n = 6, alors Edges = {{1, 2}, {2, 3} , {2, 4}, {4, 5}, {3, 6}}, vertexValues = { 1, 2, 3, 4, 5, 6} alors la sortie sera 15, 3 1 2 4 5 6 car nous pouvons mettre les valeurs de 0 à n – 1 de la manière indiquée 3 1 2 4 5 6 au sommet.

Pour résoudre ce problème, nous suivrons les étapes suivantes -

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])

Copier après la connexion

Exemple

Voyons l'implémentation suivante pour une meilleure compréhension -

#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;
}

Copier après la connexion

Input

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

Copier après la connexion

Output

15
3 1 2 4 5 6

Copier après la connexion

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!