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

Algorytmy grafowe, program o mleczarni

VPS Starter Arubacloud
0 głosów
214 wizyt
pytanie zadane 4 grudnia 2016 w C i C++ przez martix3 Użytkownik (690 p.)
Mam takie zadanie. Wiem, że trzeba go zrobić używając grafów, ale nie mam pojęcia jak się do tego zabrać. Tak myślałam, że może by wykorzystać coś z cyklem Hamiltona. A może jakiś inny algorytm? Pomożecie?
Tu wstawiam treść zadania:

 

Mleczarz codziennie dostarcza mieszkańcom miejscowości zamówione porcje mleka. Miejscowości te są połączone dwukierunkowymi drogami. Twoim zadaniem jest pomóc mleczarzowi w wyznaczenie trasy, która prowadzi przez każdą drogę co najmniej raz. Połączenia między miejscowościami są założenia takie, że Twoje zadanie jest wykonalne. Dodatkowo każda droga łącząca miejscowości ma swój koszt. Mieszkańcom miejscowości zależy na tym, aby to właśnie ich miejscowości były zaopatrzone w mleko najwcześniej jak się da. Dlatego każda miejscowość ma umowę z mleczarzem: Jeśli miejscowość jest odwiedzona przez mleczarza jako k-ta różna miejscowość na trasie i kw(i), to mleczarnia płaci k-w(i) złotych miejscowości. Ponadto mleczarnia płaci mleczarzowi 1 złotych za przybycie każdej drogi na trasie. Jest n miejscowości ponumerowanych od 1 do n. Mleczarnia jest zlokalizowana w miejscowości o numerze 1. Trasa mleczarza zaczyna się i kończy w miejscowości o numerze 1. Każda miejscowość jest usytuowana albo na przecięciu dwóch dróg albo na przecięciu czterech dróg albo jedna droga przechodzi przez miejscowość (tzn. z każdej miejscowości wychodzi 2, 4, 8 dróg). Może być klika dróg łączących dwie te same miejscowości i drogi mogą tworzyć pętle. Tzn, drogi mogą łączyć miejscowości same ze sobą. Celem zdania jest napisanie programu, który czyta opis miejscowości i dróg je łączących i wyznacza taką trasę, która prowadzi przez każdą miejscowość i każdą drogę co najmniej raz i przynosi mleczarni największy zysk netto(po odjęciu kosztów związanych z umową z miejscowościami i opłatą mleczarza). Jeżeli istnieje wiele możliwości rozwiązań, to program powinien określi dowolną. Wejście Dane są podane pliku tekstowym. W pierwszym pliku danych znajdują się dwie liczby całkowite n i m oddzielone spacją: 1<=n<=200 jest liczbą miejscowości, a m jest liczbą dróg. W każdej z następnych n linii znajduje się dodatni liczba całkowita. Linia o numerze i+1 zawiera w(i), gdzie 0<=w(i)<=1000, określa wysokość opłaty jakiej dokonuje miejscowość o numerze i. W każdej z następnych m linii znajdują się dwie dodatnie liczby całkowite oddzielone spacją, określające drogi (bezpośrednia połączenia pomiędzy miejscowościami). Wyjście Wynik powinien być zapisywany do pliku wyjściowego. W pierwszej linii znajduje się dodatnia liczba całkowita k-łącza długość trasy. Następna linia powinna zawierać k+1 odpowiadającym numerom miejscowości na trasie oddzielonych pojedynczą spacją. Pierwsza i ostatnia miejscowość trasy powinna mieć numer 1. Przykład danych wejściowych

7 11

1

2

5

1

12

2

3

1 2

7 7

2 5

3 7

4 3

1 4

5 2

2 3

3 6

6 6

6 7

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów
1 odpowiedź 301 wizyt
pytanie zadane 28 czerwca 2020 w Algorytmy przez xdelvis Nowicjusz (120 p.)
0 głosów
0 odpowiedzi 71 wizyt
0 głosów
0 odpowiedzi 228 wizyt
pytanie zadane 3 października 2020 w Algorytmy przez wojtek_suchy Mądrala (6,880 p.)

92,452 zapytań

141,262 odpowiedzi

319,085 komentarzy

61,854 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!

...