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

Zad algorytmika - Blokady

Aruba Cloud - Virtual Private Server VPS
0 głosów
252 wizyt
pytanie zadane 29 października 2023 w C i C++ przez VNC Nowicjusz (240 p.)

Witam,

Mam takie o to zadanie:

Dawno, dawno temu był sobie kraj mlekiem i miodem płynacy z rozkoszami, jakich nikt nigdy nie zaznał, gdzie problemy NP-zupełne rozwiazywało sie w czasie liniowym. Kraj ten zwał sie Bajtocja. Bajtocja składa sie z N miast połaczonych siecia dwukierunkowych dróg, w taki sposób, ze miedzy kazdymi dwoma miastami mozna przejechac tylko na jeden sposób bez zawracania.
      Król Bajtazar, aby poprawic humor sobie i swoim poddanym postanowił odnowic najwieksza ilosc dróg w Bajtocji. Niestety, nie pomyslał o tym, ze aby odnowic droge, nalezy najpierw ja zamknac. Poddani oburzyli sie, ze siec dróg bedzie zamknieta. Król bojac sie o swoja popularnosc ogłosił, ze dla kazdego miasta zamknie maksymalnie jedna droge, która przechodzi przez to miasto. Jednoczesnie jednak chce dokonac renowacji najwiekszej liczby dróg. Pomóz mu!
      Napisz program, który: wczyta ilosc miast w Bajtocji oraz opis dróg miedzy miastami, wyznaczy maksymalna liczbe dróg, która mozna poddac naprawom i wypisze wynik na standardowe wyjscie.
WEJSCIE
      W pierwszym wierszu znajduje sie jedna liczba naturalna N , okreslajaca liczbe miast. W kolejnych  N − 1 wierszach znajduje sie opis sieci dróg w Bajtocji. Opis kazdej drogi składa sie z dwóch liczb naturalnych u i v, oddzielonych pojedynczym odstepem i okreslajacych numery miast, które połaczone sa dana droga.
      Miasta numerowane sa kolejnymi liczbami naturalnymi od 1 do N (włacznie).
WYJSCIE
Twój program powinien wypisac na wyjscie dokładnie jedna liczbe całkowita — maksymalna liczbe dróg, które zostana poddane naprawom.
OGRANICZENIA
1 <= N <= 200 000.
PRZYKŁAD
Wejscie

8
1 2
2 3
2 4
3 7
4 5
4 6
6 8

Wyjscie

4

 

Udalo mi sie dojsc tylko do tego, ze ten graf da sie przedstawic jako drzewo.

Z gory dziekuje za wszystkie odpowiedzi.

2 odpowiedzi

0 głosów
odpowiedź 5 listopada 2023 przez Whistleroosh Maniak (57,400 p.)
Zadanie wygląda na programowanie dynamiczne. Ukorzenimy drzewo w wierzchołku 1. Mamy takie stany:

dp[v][0] - maksymalna liczba dróg do naprawy w poddrzewie ukorzenionym w wierzchołku v, zakładając że nie remontujemy drogi między v a którymś z jego dzieci

dp[v][1] - tak samo jak wcześniej, ale zakładamy, że remontujemy jakąś drogę między v i którymś jego dzieckiem

Pozostało wymyślić jak liczyć dp
–1 głos
odpowiedź 5 listopada 2023 przez Michał Kazula Pasjonat (19,540 p.)

No da się przedstawić to za pomocą grafu

I jak mam być szczery to wynik nie jest zgodny z założeniem (opisem).


Król bojac sie o swoja popularnosc ogłosił, ze dla kazdego miasta zamknie maksymalnie jedna droge, która przechodzi przez to miasto.

Zwróć uwagę na to co pogrubiłem. Nie da się zamknąć tylko jednej drogi. 2,4 i 6 mają zamknięte po dwie drogi aby wynik wyniósł 4.

komentarz 5 listopada 2023 przez VNC Nowicjusz (240 p.)
edycja 5 listopada 2023 przez VNC
Zacznijmy od tego, ze graf na rysunku jest skierowany, a powinnien byc nieskierowany. Wynik jest zgody z zalozeniem, mozna usunac droge nr. 1 (1-2), 4 (3-7), 5 (4-5) i 7 (6-8), wtedy dla kazdego miasta zostala usunieta maksymalnie jedna droga polaczona z nim.
komentarz 5 listopada 2023 przez Michał Kazula Pasjonat (19,540 p.)

To że jest skierowany to efekt korzystania z narzędzia do generowania grafów wink

Jeżeli weźmiemy pod uwagę pojedyncze drogi to ma to sens.

Podobne pytania

0 głosów
1 odpowiedź 195 wizyt
pytanie zadane 21 sierpnia 2023 w C i C++ przez VNC Nowicjusz (240 p.)
0 głosów
2 odpowiedzi 628 wizyt
0 głosów
2 odpowiedzi 370 wizyt
pytanie zadane 10 listopada 2016 w Algorytmy przez BlueWee Użytkownik (730 p.)

93,329 zapytań

142,323 odpowiedzi

322,400 komentarzy

62,662 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

Wprowadzenie do ITsec, tom 1 Wprowadzenie do ITsec, tom 2

Można już zamawiać dwa tomy książek o ITsec pt. "Wprowadzenie do bezpieczeństwa IT" - mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy aż 15% zniżki! Dziękujemy ekipie Sekuraka za fajny rabat dla naszej Społeczności!

...