C++-Programm zum Ermitteln der Maximalsumme eines minimal zusammenhängenden Diagramms

Angenommen, wir haben einen minimal zusammenhängenden Graphen. Das bedeutet, dass durch das Löschen einer Kante die Verbindung zum Diagramm unterbrochen wird. Der Graph hat n Eckpunkte und die Kanten sind im Array „Kanten“ angegeben. Wir erhalten außerdem ein Array „vertexValues“, das n ganzzahlige Werte enthält.

Jetzt machen wir Folgendes:

• Wir schreiben an jedem Scheitelpunkt eine positive ganze Zahl und versuchen dann, einen Bruch zu berechnen.

• Es gibt eine Kante, die zwei Eckpunkte verbindet, und wir geben den kleineren Wert der beiden Eckpunkte auf die Kante.

• Wir berechnen die Punktzahl, indem wir alle Kantenwerte addieren.

Wir müssen den Maximalwert finden, der erreicht werden kann, indem wir den Wert auf den Scheitelpunkt legen. Wir müssen den maximalen Gesamtwert und den Wert drucken, der in den Scheitelpunkt geschrieben werden soll.

Wenn die Eingabe also etwa n = 6 ist, dann ist Edges = {{1, 2}, {2, 3} , {2, 4}, {4, 5}, {3, 6}}, vertexValues ​​​​= { 1, 2, 3, 4, 5, 6} dann ist die Ausgabe 15, 3 1 2 4 5 6, da wir die Werte von 0 bis n – 1 auf die angegebene Weise 3 1 2 4 setzen können 5 6 auf der Spitze.

Um dieses Problem zu lösen, werden wir die folgenden Schritte ausführen:

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

Beispiel

Sehen wir uns zum besseren Verständnis die folgende Implementierung an:

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

Eingabe

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

Ausgabe

15
3 1 2 4 5 6

Das obige ist der detaillierte Inhalt vonC++-Programm zum Ermitteln der Maximalsumme eines minimal zusammenhängenden Diagramms. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!