Question

Program in c++
Se dă lista muchiilor unui graf neorientat ponderat. Să se determine vârful pentru care
suma ponderilor muchiilor incidente este minimă. Dacă există mai multe vârfuri cu
aceeași medie minimă, se va afișa vârful numerotat cu o valoare mai mică.

Answer 1

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

// definim structura pentru o muchie din graf

struct Edge {

 int u, v, w;

};

// functia care compara muchiile dupa ponderile lor

bool cmp(Edge a, Edge b) {

 return a.w < b.w;

}

int main() {

 int n, m;

 cin >> n >> m; // citim numarul de noduri si de muchii

 // vectorul de muchii

 vector<Edge> edges;

 // citim muchiile din graf

 for (int i = 0; i < m; i++) {

   int u, v, w;

   cin >> u >> v >> w;

   edges.push_back({u, v, w});

 }

 // sortam vectorul de muchii crescator dupa ponderi

 sort(edges.begin(), edges.end(), cmp);

 // vectorul care retine suma ponderilor muchiilor incidente pentru fiecare nod

 vector<int> sums(n + 1, 0);

 // parcurgem muchiile din graf in ordinea ponderilor crescatoare

 for (int i = 0; i < m; i++) {

   int u = edges[i].u, v = edges[i].v, w = edges[i].w;

   sums[u] += w; // adaugam ponderile muchiei la suma ponderilor incidente pentru nodul u

   sums[v] += w; // adaugam ponderile muchiei la suma ponderilor incidente pentru nodul v

 }

 // determinam nodul cu suma ponderilor incidente minima

 int min_sum = sums[1], min_node = 1;

 for (int i = 2; i <= n; i++) {

   if (sums[i] < min_sum) {

     min_sum = sums[i];

     min_node = i;

   }

 }

 cout << "Nodul cu suma ponderilor incidente minima este: " << min_node << endl;

 return 0;

}

Această implementare creează un vector sums care retine suma ponderilor muchiilor incidente pentru fiecare nod din graf. Apoi, parcurgem vectorul de muchii sortat crescător după ponderile lor și adăugăm ponderile fiecărei muchii la suma ponderilor incidente pentru nodurile respective. La final, se determină nodul cu suma ponderilor incidente minimă și se afișează.