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	#63116998	Utilizator	Dabu Matei (m_at_eI)
Fișier	esentiale.cpp	Dimensiune	756 B
Data încărcării	15 Februarie 2026, 15:40	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

esentiale.cpp:5:43: error: template argument 1 is invalid
 queue < pair < int , pair < int , int > > v;

                                           ^
esentiale.cpp:5:43: error: template argument 2 is invalid
esentiale.cpp: In function 'int fi(int)':
esentiale.cpp:8:8: error: 't' was not declared in this scope
     if(t[x]==x)

        ^
esentiale.cpp: In function 'int main()':
esentiale.cpp:21:9: error: 't' was not declared in this scope
         t[i]=i;

         ^
esentiale.cpp:24:12: error: 'a' was not declared in this scope
         f>>a>>b>>c;

            ^
esentiale.cpp:24:15: error: 'b' was not declared in this scope
         f>>a>>b>>c;

               ^
esentiale.cpp:25:9: error: 'v' was not declared in this scope
         v.push_back(pair(c,make_pair(a,b)));

         ^
esentiale.cpp:25:25: error: missing template arguments before '(' token
         v.push_back(pair(c,make_pair(a,b)));

                         ^
esentiale.cpp:27:10: error: 'v' was not declared in this scope
     sort(v.begin(),v.end());

          ^
esentiale.cpp:28:5: error: 'k' was not declared in this scope
     k=0;

     ^
esentiale.cpp:34:9: error: 't' was not declared in this scope
         t[c1]=fi(c1);

         ^
esentiale.cpp:18:23: warning: unused variable 'j' [-Wunused-variable]
     int n,m,cerinta,i,j,c;

                       ^
esentiale.cpp: In function 'int fi(int)':
esentiale.cpp:15:1: warning: control reaches end of non-void function [-Wreturn-type]
 }

 ^

Cum funcționează evaluarea?