• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie z Grafami potrafię zrobić lepiej test niż zadanie wzorcowe (więc czegoś nie rozumiem)

VPS Starter Arubacloud
0 głosów
385 wizyt
pytanie zadane 3 stycznia 2021 w Algorytmy przez wojtek_suchy Mądrala (6,880 p.)

Mam takie zdanie: https://codeforces.com/problemset/problem/1466/D

I taką odpowiedź: https://codeforces.com/blog/entry/86126

Ale dla takiego grafu:

5
10 12 3 5 4
1 2
1 4
1 5
2 3

Potafię znaleźć rozwiązanie lepsze niż wzorcowe

Nigdzie w zadaniu nie mogę znaleźć że wierzołki jednego koloru muszą być spójne, dlaczego nie mogę zrobić tego tak jak pokazałęm na rysunku?

2 odpowiedzi

+2 głosów
odpowiedź 3 stycznia 2021 przez Whistleroosh Maniak (56,900 p.)
wybrane 3 stycznia 2021 przez wojtek_suchy
 
Najlepsza
Wynik dla danego koloru to max z wyników dla wszystkich spójnych pokolorowanych danym kolorem. Czyli w tym drugim przypadku kolorem czerwonym rozbijasz graf i tworzysz dwie czarne spójne. W jednej czarnej spójnej wynikiem jest 19 a w drugiej 15, więc max z tego to 19 co daje wynik 19 + 22, czyli 41
0 głosów
odpowiedź 3 stycznia 2021 przez Wiciorny Ekspert (269,120 p.)

Wynika to nie wprost z definicji tego, że w zadaniu masz informacje o tym, że jest to 'tree' czyli drzewo.

Z definicji wynika: W tym zadaniu otrzymujesz drzewo z n ważonymi wierzchołkami. Drzewo to połączony graf z n − 1n − 1 krawędziami.

 

Graf prosty G jest drzewem jedynie, jeśli spełnia jeden z warunków:

  • dowolne dwa wierzchołki łączy dokładnie jedna ścieżka prosta.
  • G jest acykliczny i dodanie krawędzi łączącej dowolne dwa wierzchołki utworzy cykl.
  • G jest spójny i usunięcie dowolnej krawędzi spowoduje, że G przestanie być spójny

Podobne pytania

0 głosów
1 odpowiedź 114 wizyt
pytanie zadane 11 września 2020 w Algorytmy przez wojtek_suchy Mądrala (6,880 p.)
0 głosów
1 odpowiedź 265 wizyt
pytanie zadane 18 stycznia 2023 w C i C++ przez polandonion Mądrala (6,970 p.)
0 głosów
1 odpowiedź 213 wizyt
pytanie zadane 13 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...