Informatyczny kącik olimpijski

Od przybytku głowa (nie) boli

Tym razem dwa zadania „z haczykiem”.

Pierwsze zadanie (VI Olimpiada Informatyczna):

Co z zadaniem drugim, które, jak wszystkie problemy optymalizacyjne, wydaje się trudniejsze?

Narzędzia
Obiekty
Słowa kluczowe
Kategoria: Informatyka

Od przybytku głowa (nie) boli»Zadanie 2

o zadaniu...

Zadanie olimpijskie: BOI 2001
Zadanie pochodzi z artykułu Od przybytku głowa (nie) boli
Publikacja w Delcie: marzec 2008
Publikacja elektroniczna: 20-12-2010

Wiejski listonosz roznosi pocztę po okolicy. Każda wieś leży przy drodze albo na przecięciu dwóch lub czterech dróg, zatem można z niej wyjść w 2, 4 lub 8 kierunkach (niektóre drogi mogą prowadzić ze wsi do niej samej, a pomiędzy dwiema wsiami może być więcej niż jedna bezpośrednia droga). Budynek poczty jest w jednej ze wsi. Listonosz musi odwiedzić wszystkie wsie, a ponadto musi przejść wzdłuż wszystkich dróg (przy nich też stoją domy) i wrócić na pocztę. Za przejście każdej mili poczta płaci listonoszowi 1EUR. Ponadto mieszkańcy każdej wsi chcą, aby listonosz odwiedził ich jak najwcześniej, dlatego poczta zawarła z każdą ze wsi (wsie numerujemy liczbami $\text{[math]}$ ) umowę, w której określona jest pewna liczba $\text{[math]}$ : mianowicie, jeśli listonosz odwiedzi wieś numer $\text{[math]}$ jako $\text{[math]}$ -tą w kolejności (tzn. odwiedził wcześniej dokładnie $\text{[math]}$ różnych innych wsi) oraz $\text{[math]}$ to wieś dopłaca poczcie $\text{[math]}$ EUR, a jeśli $\text{[math]}$ to poczta karnie płaci wsi $\text{[math]}$ EUR. Jak wyznaczyć trasę listonosza, aby zmaksymalizować zysk (ew. zminimalizować stratę) poczty? Na wejściu mamy daną liczbę wsi $\text{[math]}$ , opis grafu dróg i umówione wartości $\text{[math]}$ , $\text{[math]}$