Rezumat problemă

WeightDif

#4419

Se dă un graf conex neorientat G cu N noduri și M muchii, fiecare muchie având asociat un cost. Un arbore parțial pentru G este un subgraf cu structura de arbore, care cuprinde toate nodurile și o parte din muchii. Se cere găsirea unui arbore parțial al grafului G, astfel încât diferența dintre cel mai mare și cel mai mic cost al unei muchii să fie minimă.

Urmașii lui Moisil 2023, clasele XI-XII

Fișiere Pracsiu Dan (dnprx) Ovidiu Rața concurs

Clasa 11 Teoria Grafurilor Grafuri cu costuri Păduri de mulțimi disjuncte Cautare binara

Rezolvă

Detalii

Problema	WeightDif	Operații I/O	weightdif.in/weightdif.out
Limita timp	3 secunde	Limita memorie	Total: 256 MB / Stivă 64 MB
Id soluție	#63801428	Utilizator	Tanase Cristian (Cristian079877)
Fișier	weightdif.cpp	Dimensiune	2.87 KB
Data încărcării	19 Martie 2026, 12:08	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

weightdif.cpp: In function 'int bfs(int, int)':
weightdif.cpp:48:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v1[nod].size();i++)

                                ^
weightdif.cpp:50:25: error: request for member 'first' in 'v1[nod].std::vector<_Tp, _Alloc>::operator[]<int, std::allocator<int> >(((std::vector<int>::size_type)i))', which is of non-class type '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}'
         if(p[v1[nod][i].first]!=parinte)

                         ^
weightdif.cpp:51:24: error: request for member 'first' in 'v1[nod].std::vector<_Tp, _Alloc>::operator[]<int, std::allocator<int> >(((std::vector<int>::size_type)i))', which is of non-class type '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}'
         bfs(v1[nod][i].first,parinte);

                        ^
weightdif.cpp:53:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }

 ^
weightdif.cpp: In function 'int main()':
weightdif.cpp:75:30: error: no matching function for call to 'std::vector<int>::push_back(<brace-enclosed initializer list>)'
         v1[a].push_back({b,c});

                              ^
weightdif.cpp:75:30: 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 weightdif.cpp:1:
/usr/include/c++/4.8/bits/stl_vector.h:901:7: note: void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = int]
       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 int&}'
/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 = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = int]
       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<int>::value_type&& {aka int&&}'
weightdif.cpp:76:30: error: no matching function for call to 'std::vector<int>::push_back(<brace-enclosed initializer list>)'
         v1[b].push_back({a,c});

                              ^
weightdif.cpp:76:30: 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 weightdif.cpp:1:
/usr/include/c++/4.8/bits/stl_vector.h:901:7: note: void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = int]
       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 int&}'
/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 = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = int]
       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<int>::value_type&& {aka int&&}'
weightdif.cpp:98:53: error: converting to 'std::vector<std::tuple<int, int, int> >::value_type {aka std::tuple<int, int, int>}' from initializer list would use explicit constructor 'constexpr std::tuple< <template-parameter-1-1> >::tuple(_UElements&& ...) [with _UElements = {int&, int&, int&}; <template-parameter-2-2> = void; _Elements = {int, int, int}]'
             afis.push_back({v[i].x,v[i].y,v[i].cost});

                                                     ^
weightdif.cpp:110:20: error: '__gnu_cxx::__alloc_traits<std::allocator<std::tuple<int, int, int> > >::value_type' has no member named 'first'
        p[afis[i-1].first]=afis[i-1].first;

                    ^
weightdif.cpp:110:37: error: '__gnu_cxx::__alloc_traits<std::allocator<std::tuple<int, int, int> > >::value_type' has no member named 'first'
        p[afis[i-1].first]=afis[i-1].first;

                                     ^
weightdif.cpp:111:21: error: '__gnu_cxx::__alloc_traits<std::allocator<std::tuple<int, int, int> > >::value_type' has no member named 'second'
         p[afis[i-1].second]=afis[i-1].second;

                     ^
weightdif.cpp:111:39: error: '__gnu_cxx::__alloc_traits<std::allocator<std::tuple<int, int, int> > >::value_type' has no member named 'second'
         p[afis[i-1].second]=afis[i-1].second;

                                       ^
weightdif.cpp:112:23: error: '__gnu_cxx::__alloc_traits<std::allocator<std::tuple<int, int, int> > >::value_type' has no member named 'first'
         bfs(afis[i-1].first,afis[i-1].first);

                       ^
weightdif.cpp:112:39: error: '__gnu_cxx::__alloc_traits<std::allocator<std::tuple<int, int, int> > >::value_type' has no member named 'first'
         bfs(afis[i-1].first,afis[i-1].first);

                                       ^
weightdif.cpp:113:24: error: '__gnu_cxx::__alloc_traits<std::allocator<std::tuple<int, int, int> > >::value_type' has no member named 'second'
          bfs(afis[i-1].second,afis[i-1].second);

                        ^
weightdif.cpp:113:41: error: '__gnu_cxx::__alloc_traits<std::allocator<std::tuple<int, int, int> > >::value_type' has no member named 'second'
          bfs(afis[i-1].second,afis[i-1].second);

                                         ^
weightdif.cpp:115:34: error: lvalue required as left operand of assignment
         for(j=ultimul+i+1;j<m&&ok=0;j++)

                                  ^
weightdif.cpp:126:26: error: '__gnu_cxx::__alloc_traits<std::allocator<std::tuple<int, int, int> > >::value_type' has no member named 'third'
         minim=afis[cont].third;

                          ^
weightdif.cpp:58:21: warning: unused variable 'total' [-Wunused-variable]
     int n,m,i,a,b,c,total=0,nr=0,minim=INT_MAX,maxim=INT_MIN,rez=INT_MAX,j,k,ultimul,ok,cont;

                     ^
weightdif.cpp: In function 'int unite(int, int)':
weightdif.cpp:30:1: warning: control reaches end of non-void function [-Wreturn-type]
 }

 ^
weightdif.cpp: In function 'bool crit(muchie, muchie)':
weightdif.cpp:43:1: warning: control reaches end of non-void function [-Wreturn-type]
 }

 ^

Cum funcționează evaluarea?