Heim > Backend-Entwicklung > C++ > C++-Programm zum Ermitteln der Maximalsumme eines minimal zusammenhängenden Diagramms

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

WBOY
Freigeben: 2023-09-13 13:53:13
nach vorne
1164 Leute haben es durchsucht

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])
Nach dem Login kopieren

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;
}
Nach dem Login kopieren

Eingabe

6, {{1, 2}, {2, 3}, {2, 4}, {4, 5}, {3, 6}}, {1, 2, 3, 4, 5, 6}
Nach dem Login kopieren

Ausgabe

15
3 1 2 4 5 6
Nach dem Login kopieren

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!

Quelle:tutorialspoint.com
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage