Rezumat problemă

esentiale

#4950

Fie G un graf neorientat conex cu N noduri și M muchii. Nodurile sunt numerotate de la 1 la N iar muchiile au asociate costuri numere naturale date. Un graf parţial al lui G conex şi fără cicluri este denumit arbore parţial. Costul unui arbore parțial este suma costurilor muchiilor arborelui. Deoarece unele muchii pot avea aceelași cost, este posibil ca graful G să aibă mai mulți arbori parțiali de cost minim. Definim o muchie a grafului G ca fiind esențială dacă ea face parte din toți arborii parțiali de cost minim ai lui G. Scrieţi un program care, cunoscând graful, rezolvă următoarele două cerinţe:
1. determină costul unui arbore parțial de cost minim al lui G;
2. determină numărul de muchii esențiale ale grafului G.

OMI 2026, clasele 11-12

Fișiere Pracsiu Dan (dnprx) Paul Diac concurs

Clasa 11 Teoria Grafurilor Grafuri cu costuri Algoritmul lui Kruskal

Rezolvă

Detalii

Problema	esentiale	Operații I/O	esentiale.in/esentiale.out
Limita timp	0.5 secunde	Limita memorie	Total: 64 MB / Stivă 16 MB
Id soluție	#64118708	Utilizator	Dragos Eric (GigiMustar)
Fișier	esentiale.cpp	Dimensiune	1.82 KB
Data încărcării	18 Aprilie 2026, 11:21	Scor/rezultat	100 puncte

Evaluare

Mesaj compilare

esentiale.cpp: In function ‘std::pair<long long int, std::vector<int> > kruskal()’:
esentiale.cpp:44:21: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::tuple<int, int, int, bool> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   44 |     for(int i = 0; i<edges.size(); i++){
      |                    ~^~~~~~~~~~~~~
esentiale.cpp:45:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   45 |         auto [c,x,y,skip] = edges[i];
      |              ^
esentiale.cpp:54:23: warning: comparison of integer expressions of different signedness: ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} and ‘long long int’ [-Wsign-compare]
   54 |         if(apm.size() == n-1) break;
      |            ~~~~~~~~~~~^~~~~~
esentiale.cpp: In function ‘int main()’:
esentiale.cpp:62:10: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   62 |     auto [cost_min, apm_idx] = kruskal();
      |          ^
esentiale.cpp:71:40: warning: comparison of integer expressions of different signedness: ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} and ‘long long int’ [-Wsign-compare]
   71 |             if(kruskal().second.size() < n-1 || kruskal().first > cost_min) cnt++;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Rezultat evaluare

Cum funcționează evaluarea?