#592
Kruskal
Se dă un graf neorientat ponderat conex cu n
vârfuri și m
muchii – în care fiecare muchie are asociat un cost, număr natural strict pozitiv. Folosind algoritmul lui Kruskal, determinați un arbore parțial de cost minim.
Problema | Kruskal | Operații I/O |
kruskal.in /kruskal.out
|
---|---|---|---|
Limita timp | 0.1 secunde | Limita memorie |
Total: 64 MB
/
Stivă 8 MB
|
Id soluție | #29255373 | Utilizator | |
Fișier | kruskal.cpp | Dimensiune | 1.50 KB |
Data încărcării | 12 Aprilie 2021, 12:37 | Scor / rezultat | Eroare de compilare |
In file included from /usr/include/c++/4.8/algorithm:62:0, from kruskal.cpp:4: /usr/include/c++/4.8/bits/stl_algo.h: In instantiation of '_RandomAccessIterator std::__unguarded_partition(_RandomAccessIterator, _RandomAccessIterator, const _Tp&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Muchie*, std::vector<Muchie> >; _Tp = Muchie]': /usr/include/c++/4.8/bits/stl_algo.h:2283:70: required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Muchie*, std::vector<Muchie> >]' /usr/include/c++/4.8/bits/stl_algo.h:2315:54: required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Muchie*, std::vector<Muchie> >; _Size = int]' /usr/include/c++/4.8/bits/stl_algo.h:5461:36: required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Muchie*, std::vector<Muchie> >]' kruskal.cpp:27:33: required from here /usr/include/c++/4.8/bits/stl_algo.h:2242:20: error: no match for 'operator<' (operand types are 'Muchie' and 'const Muchie') while (*__first < __pivot) ^ /usr/include/c++/4.8/bits/stl_algo.h:2242:20: note: candidates are: kruskal.cpp:13:7: note: bool Muchie::operator<(Muchie&) bool operator<(Muchie& ot) { return this->w < ot.w; }; ^ kruskal.cpp:13:7: note: no known conversion for argument 1 from 'const Muchie' to 'Muchie&' In file included from /usr/include/c++/4.8/bits/stl_algobase.h:64:0, from /usr/include/c++/4.8/bits/char_traits.h:39, from /usr/include/c++/4.8/ios:40, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from kruskal.cpp:1: /usr/include/c++/4.8/bits/stl_pair.h:220:5: note: template<class _T1, class _T2> constexpr bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&) operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) ^ /usr/include/c++/4.8/bits/stl_pair.h:220:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/4.8/algorithm:62:0, from kruskal.cpp:4: /usr/include/c++/4.8/bits/stl_algo.h:2242:20: note: 'Muchie' is not derived from 'const std::pair<_T1, _T2>' while (*__first < __pivot) ^ In file included from /usr/include/c++/4.8/bits/stl_algobase.h:67:0, from /usr/include/c++/4.8/bits/char_traits.h:39, from /usr/include/c++/4.8/ios:40, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from kruskal.cpp:1: /usr/include/c++/4.8/bits/stl_iterator.h:297:5: note: template<class _Iterator> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&) operator<(const reverse_iterator<_Iterator>& __x, ^ /usr/include/c++/4.8/bits/stl_iterator.h:297:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/4.8/algorithm:62:0, from kruskal.cpp:4: /usr/include/c++/4.8/bits/stl_algo.h:2242:20: note: 'Muchie' is not derived from 'const std::reverse_iterator<_Iterator>' while (*__first < __pivot) ^ In file included from /usr/include/c++/4.8/bits/stl_algobase.h:67:0, from /usr/include/c++/4.8/bits/char_traits.h:39, from /usr/include/c++/4.8/ios:40, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from kruskal.cpp:1: /usr/include/c++/4.8/bits/stl_iterator.h:347:5: note: template<class _IteratorL, class _IteratorR> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&) operator<(const reverse_iterator<_IteratorL>& __x, ^ /usr/include/c++/4.8/bits/stl_iterator.h:347:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/4.8/algorithm:62:0, from kruskal.cpp:4: /usr/include/c++/4.8/bits/stl_algo.h:2242:20: note: 'Muchie' is not derived from 'const std::reverse_iterator<_Iterator>' while (*__first < __pivot) ^ In file included from /usr/include/c++/4.8/bits/stl_algobase.h:67:0, from /usr/include/c++/4.8/bits/char_traits.h:39, from /usr/include/c++/4.8/ios:40, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from kruskal.cpp:1: /usr/include/c++/4.8/bits/stl_iterator.h:1055:5: note: template<class _IteratorL, class _IteratorR> bool std::operator<(const std::move_iterator<_Iterator>&, const std::move_iterator<_IteratorR>&) operator<(const move_iterator<_IteratorL>& __x, ^ /usr/include/c++/4.8/bits/stl_iterator.h:1055:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/4.8/algorithm:62:0, from kruskal.cpp:4: /usr/include/c++/4.8/bits/stl_algo.h:2242:20: note: 'Muchie' is not derived from 'const std::move_iterator<_Iterator>' while (*__first < __pivot) ^ In file included from /usr/include/c++/4.8/bits/stl_algobase.h:67:0, from /usr/include/c++/4.8/bits/char_traits.h:39, from /usr/include/c++/4.8/ios:40, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from kruskal.cpp:1: /usr/include/c++/4.8/bits/stl_iterator.h:1061:5: note: template<class _Iterator> bool std::operator<(const std::move_iterator<_Iterator>&, const std::move_iterator<_Iterator>&) operator<(const move_iterator<_Iterator>& __x, ^ /usr/include/c++/4.8/bits/stl_iterator.h:1061:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/4.8/algorithm:62:0, from kruskal.cpp:4: /usr/include/c++/4.8/bits/stl_algo.h:2242:20: note: 'Muchie' is not derived from 'const std::move_iterator<_Iterator>' while (*__first < __pivot) ^ In file included from /usr/include/c++/4.8/string:52:0, from /usr/include/c++/4.8/bits/locale_classes.h:40, from /usr/include/c++/4.8/bits/ios_base.h:41, from /usr/include/c++/4.8/ios:42, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from kruskal.cpp:1: /usr/include/c++/4.8/bits/basic_string.h:2569:5: note: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::basic_string<_CharT, _Traits, _Alloc>&, const std::basic_string<_CharT, _Traits, _Alloc>&) operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs, ^ /usr/include/c++/4.8/bits/basic_string.h:2569:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/4.8/algorithm:62:0, from kruskal.cpp:4: /usr/include/c++/4.8/bits/stl_algo.h:2242:20: note: 'Muchie' is not derived from 'const std::basic_string<_CharT, _Traits, _Alloc>' while (*__first < __pivot) ^ In file included from /usr/include/c++/4.8/string:52:0, from /usr/include/c++/4.8/bits/locale_classes.h:40, from /usr/include/c++/4.8/bits/ios_base.h:41, from /usr/include/c++/4.8/ios:42, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from kruskal.cpp:1: /usr/include/c++/4.8/bits/basic_string.h:2581:5: note: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::basic_string<_CharT, _Traits, _Alloc>&, const _CharT*) operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs, ^ /usr/include/c++/4.8/bits/basic_string.h:2581:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/4.8/algorithm:62:0, from kruskal.cpp:4: /usr/include/c++/4.8/bits/stl_algo.h:2242:20: note: 'Muchie' is not derived from 'const std::basic_string<_CharT, _Traits, _Alloc>' while (*__first < __pivot) ^ In file included from /usr/include/c++/4.8/string:52:0, from /usr/include/c++/4.8/bits/locale_classes.h:40, from /usr/include/c++/4.8/bits/ios_base.h:41, from /usr/include/c++/4.8/ios:42, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from kruskal.cpp:1: /usr/include/c++/4.8/bits/basic_string.h:2593:5: note: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const _CharT*, const std::basic_string<_CharT, _Traits, _Alloc>&) operator<(const _CharT* __lhs, ^ /usr/include/c++/4.8/bits/basic_string.h:2593:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/4.8/algorithm:62:0, from kruskal.cpp:4: /usr/include/c++/4.8/bits/stl_algo.h:2242:20: note: mismatched types 'const _CharT*' and 'Muchie' while (*__first < __pivot) ^ In file included from /usr/include/c++/4.8/vector:64:0, from kruskal.cpp:3: /usr/include/c++/4.8/bits/stl_vector.h:1421:5: note: template<class _Tp, class _Alloc> bool std::operator<(const std::vector<_Tp, _Alloc>&, const std::vector<_Tp, _Alloc>&) operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) ^ /usr/include/c++/4.8/bits/stl_vector.h:1421:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/4.8/algorithm:62:0, from kruskal.cpp:4: /usr/include/c++/4.8/bits/stl_algo.h:2242:20: note: 'Muchie' is not derived from 'const std::vector<_Tp, _Alloc>' while (*__first < __pivot) ^ In file included from /usr/include/c++/4.8/tuple:39:0, from /usr/include/c++/4.8/functional:55, from /usr/include/c++/4.8/bits/stl_algo.h:66, from /usr/include/c++/4.8/algorithm:62, from kruskal.cpp:4: /usr/include/c++/4.8/array:238:5: note: template<class _Tp, unsigned int _Nm> bool std::operator<(const std::array<_Tp, _Nm>&, const std::array<_Tp, _Nm>&) operator<(const array<_Tp, _Nm>& __a, const array<_Tp, _Nm>& __b) ^ /usr/include/c++/4.8/array:238:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/4.8/algorithm:62:0, from kruskal.cpp:4: /usr/include/c++/4.8/bits/stl_algo.h:2242:20: note: 'Muchie' is not derived from 'const std::array<_Tp, _Nm>' while (*__first < __pivot) ^ In file included from /usr/include/c++/4.8/functional:55:0, from /usr/include/c++/4.8/bits/stl_algo.h:66, from /usr/include/c++/4.8/algorithm:62, from kruskal.cpp:4: /usr/include/c++/4.8/tuple:824:5: note: template<class ... _TElements, class ... _UElements> constexpr bool std::operator<(const std::tuple<_Elements ...>&, const std::tuple<_Elements ...>&) operator<(const tuple<_TElements...>& __t, ^ /usr/include/c++/4.8/tuple:824:5: note: template argument deduction/substitution failed: In file included from /usr/include/c++/4.8/algorithm:62:0, from kruskal.cpp:4: /usr/include/c++/4.8/bits/stl_algo.h:2242:20: note: 'Muchie' is not derived from 'const std::tuple<_Elements ...>' while (*__first < __pivot) ^ /usr/include/c++/4.8/bits/stl_algo.h:2245:19: error: passing 'const Muchie' as 'this' argument of 'bool Muchie::operator<(Muchie&)' discards qualifiers [-fpermissive] while (__pivot < *__last) ^
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema Kruskal face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.