Bajtocja - I OIG

Mam problem z zadaniem Bajtocja z I etapu I OIG. http://main.edu.pl/pl/archive/oig/1/baj

Znam algorytm Kruskala oraz Prima, ale nie mam pojęcia jak zrobić te zadanie.

Trzeba po prostu skonstruować graf na podstawie danych z wejścia i wyznaczyć dla niego minimalne drzewo rozpinające.
Skoro znasz algorytmy Kruskala i Prima to nie powinieneś mieć z tym problemów.
Napisz dokładnie z czym masz problem.

Zadanie polega na odrzuceniu krawędzi, które nie należą do DOWOLNEGO minimalnego drzewa rozpinającego.

Chyba chodziło ci o KAŻDEGO, a nie DOWOLNEGO. Jeśli DOWOLNEGO to dla niektórych grafów powychodziły by ci bzury.
Np tutaj http://en.wikipedia.org/wiki/File:Multiple_minimum_spanning_trees.svg
W tym węzeł D nie byłby połączony z żadnym innym.

Według mnie to byłoby sprzeczne z "postanowił zgodzić się tylko na taką sieć, która będzie możliwie najtańsza"
ponieważ może się zdarzyć taki graf, dla którego suma wszystkich jego minimalnych drzew rozpinających będzie tworzyć cykle (lub nawet będzie równa temu grafowi). Cykle tylko zwiększą koszt budowy traktów nie powodując zmiany w dostępności miast. A o to przecież tylko chodzi.

Zapoznaj się z tym dokumentem: http://oi.edu.pl/old/html/zadania/oig1/Etap1/baj.pdf Chyba nie warto aby się ktoś inny tutaj rozpisywał.

Dobra. Mój błąd. Nie doczytałem tego
"dla każdego traktu określi, czy istnieje taka sieć połączeń między miastami, zgodna z królewskimi rozkazami i w której rozpatrywany trakt, wybudowany za wskazaną kwotę, jest wykorzystywany, "
Przepraszam.