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	#63088366	Utilizator	David Dragos Nicolae (dragosdavid)
Fișier	esentiale.cpp	Dimensiune	1.76 KB
Data încărcării	13 Februarie 2026, 10:46	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

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

                                    ^
esentiale.cpp:63:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i<irgc.size();i++){

                                   ^
esentiale.cpp:64:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(i<irgc.size()-1){

                                  ^
esentiale.cpp:67:65: error: request for member 'irgc' in 'irgc.std::vector<_Tp, _Alloc>::operator[]<san, std::allocator<san> >(((std::vector<san>::size_type)i)).san::r', which is of non-class type 'int'
                            basij.push_back({irgc[i].l,irgc[i].r.irgc[i].c})

                                                                 ^
esentiale.cpp:67:75: error: no matching function for call to 'std::vector<san>::push_back(<brace-enclosed initializer list>)'
                            basij.push_back({irgc[i].l,irgc[i].r.irgc[i].c})

                                                                           ^
esentiale.cpp:67:75: note: candidates are:
In file included from /usr/include/c++/4.8/vector:64:0,
                 from /usr/include/c++/4.8/bits/random.h:34,
                 from /usr/include/c++/4.8/random:50,
                 from /usr/include/c++/4.8/bits/stl_algo.h:65,
                 from /usr/include/c++/4.8/algorithm:62,
                 from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:64,
                 from esentiale.cpp:2:
/usr/include/c++/4.8/bits/stl_vector.h:901:7: note: void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = san; _Alloc = std::allocator<san>; std::vector<_Tp, _Alloc>::value_type = san]
       push_back(const value_type& __x)
       ^
/usr/include/c++/4.8/bits/stl_vector.h:901:7: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type& {aka const san&}'
/usr/include/c++/4.8/bits/stl_vector.h:919:7: note: void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = san; _Alloc = std::allocator<san>; std::vector<_Tp, _Alloc>::value_type = san]
       push_back(value_type&& __x)
       ^
/usr/include/c++/4.8/bits/stl_vector.h:919:7: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<san>::value_type&& {aka san&&}'
esentiale.cpp:68:25: error: expected ';' before '}' token
                         }

                         ^
esentiale.cpp:61:13: warning: unused variable 'q' [-Wunused-variable]
         int q= 0;

             ^
esentiale.cpp:62:13: warning: unused variable 'll' [-Wunused-variable]
         int ll=0;

             ^

Cum funcționează evaluarea?