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
