Heim > Artikel > Backend-Entwicklung > C++-Programm zum Ermitteln der maximalen Bewertungskomponente, die aus einem Diagramm reduziert werden kann
Angenommen, es gibt einen gewichteten ungerichteten Graphen mit n Eckpunkten und m Kanten. Der Score eines Graphen ist definiert als die Summe der Gewichte aller Kanten im Graphen. Kantengewichte können negativ sein. Wenn sie entfernt werden, erhöht sich die Bewertung des Diagramms. Was wir tun müssen, ist, die Punktzahl des Diagramms zu minimieren, indem wir Kanten im Diagramm entfernen und gleichzeitig die Konnektivität des Diagramms beibehalten. Wir müssen die maximale Punktzahl finden, die reduziert werden kann.
Der Graph wird in Form eines Arrays „Kanten“ angegeben, wobei jedes Element die Form {Gewicht, {Vertex1, Vertex2}} hat.
Wenn also die Eingabe n = 5, m = 6, Kanten = {{2, {1, 2}}, {2, {1, 3}}, {1, {2, 3}}, {3 ist , {2, 4}}, {2, {2, 5}}, {1, {3, 5}}}, dann ist die Ausgabe 4.
Wenn wir die Kanten (1, 2) und (2, 5) aus dem Diagramm entfernen, beträgt die Gesamtpunktzahlreduzierung 4 und das Diagramm bleibt weiterhin verbunden.
Um dieses Problem zu lösen, werden wir die folgenden Schritte ausführen:
cnum := 0 Define an array par of size: 100. Define an array dim of size: 100. Define a function make(), this will take v, par[v] := v dim[v] := 1 Define a function find(), this will take v, if par[v] is same as v, then: return v return par[v] = find(par[v]) Define a function unify(), this will take a, b, a := find(a) b := find(b) if a is not equal to b, then: (decrease cnum by 1) if dim[a] > dim[b], then: swap values of (a, b) par[a] := b dim[b] := dim[b] + dim[a] cnum := n sort the array edges based on edge weights for initialize i := 1, when i <= n, update (increase i by 1), do: make(i) res := 0 for each edge in edges, do: a := first vertex of edge b := second vertex of edge weight := weight of edge if find(a) is same as find(b), then: if weight >= 0, then: res := res + 1 * weight Ignore following part, skip to the next iteration if cnum is same as 1, then: if weight >= 0, then: res := res + 1 * weight Otherwise unify(a, b) return res
Sehen wir uns zum besseren Verständnis die folgende Implementierung an:
#include <bits/stdc++.h> using namespace std; int cnum = 0; int par[100]; int dim[100]; void make(int v){ par[v] = v; dim[v] = 1; } int find(int v){ if(par[v] == v) return v; return par[v] = find(par[v]); } void unify(int a, int b){ a = find(a); b = find(b); if(a != b){ cnum--; if(dim[a] > dim[b]){ swap(a, b); } par[a] = b; dim[b] += dim[a]; } } int solve(int n, int m, vector <pair <int, pair<int,int>>> edges){ cnum = n; sort(edges.begin(), edges.end()); for(int i = 1; i <= n; i++) make(i); int res = 0; for(auto &edge : edges){ int a = edge.second.first; int b = edge.second.second; int weight = edge.first; if(find(a) == find(b)) { if(weight >= 0) res += 1 * weight; continue; } if(cnum == 1){ if(weight >= 0) res += 1 * weight; } else{ unify(a, b); } } return res; } int main() { int n = 5, m = 6; vector <pair<int, pair<int,int>>> edges = {{2, {1, 2}}, {2, {1, 3}}, {1, {2, 3}}, {3, {2, 4}}, {2, {2, 5}}, {1, {3, 5}}}; cout<< solve(n, m, edges); return 0; }
5, 6, {{2, {1, 2}}, {2, {1, 3}}, {1, {2, 3}}, {3, {2, 4}}, {2, {2, 5}}, {1, {3, 5}}}
4
Das obige ist der detaillierte Inhalt vonC++-Programm zum Ermitteln der maximalen Bewertungskomponente, die aus einem Diagramm reduziert werden kann. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!