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	#63324839	Utilizator	Fulga Bogdan (bogdan_07f)
Fișier	esentiale.cpp	Dimensiune	3.43 KB
Data încărcării	26 Februarie 2026, 11:33	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

esentiale.cpp: In function 'int main()':
esentiale.cpp:86:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int k = 0; k < temp_edges.size(); k++) {

                                             ^
esentiale.cpp: In lambda function:
esentiale.cpp:100:23: error: expected unqualified-id before '[' token
             for (auto [v, id] : adj[u]) {

                       ^
esentiale.cpp:100:23: error: expected ';' before '[' token
esentiale.cpp:100:24: error: 'v' was not declared in this scope
             for (auto [v, id] : adj[u]) {

                        ^
esentiale.cpp:100:27: error: 'id' was not declared in this scope
             for (auto [v, id] : adj[u]) {

                           ^
esentiale.cpp: In lambda function:
esentiale.cpp:100:31: error: expected '{' before ':' token
             for (auto [v, id] : adj[u]) {

                               ^
esentiale.cpp: In lambda function:
esentiale.cpp:100:31: error: expected ';' before ':' token
esentiale.cpp:100:31: error: expected primary-expression before ':' token
esentiale.cpp:100:31: error: expected ')' before ':' token
esentiale.cpp:100:31: error: expected primary-expression before ':' token
esentiale.cpp:100:31: error: expected ';' before ':' token
esentiale.cpp:142:1: error: expected '}' at end of input
 }
 ^
esentiale.cpp: In function 'int main()':
esentiale.cpp:142:1: error: expected ',' or ';' at end of input
esentiale.cpp:142:1: error: expected '}' at end of input
esentiale.cpp:56:15: warning: unused variable 'mst_cost' [-Wunused-variable]
     long long mst_cost = 0;

               ^
esentiale.cpp:57:9: warning: unused variable 'essential_count' [-Wunused-variable]
     int essential_count = 0;

         ^
esentiale.cpp:142:1: error: expected '}' at end of input
 }
 ^

Cum funcționează evaluarea?