Nie wiem, jak postępować z tym problemem.
Biorąc pod uwagę graf nieskierowany z każdą krawędziąkolor czerwony lub niebieski. Jak mogę znaleźć minimalne drzewo rozpinające, które zawiera kilka czerwonych krawędzi, jak to możliwe, w złożoności czasowej (O (m + n) log n). Gdzie m wierzchołków i n to krawędzie.
Każda pomoc zostanie bardzo doceniona.
Odpowiedzi:
1 dla odpowiedzi № 1O ile widzę, myślę, że odpowiedziałeś na własne pytanie. Przez przypisanie wagi do krawędzi, czerwone wagi 1 i niebieskie wagi 0, problem staje się klasycznym odkryciem minimalne drzewo opinające, który ma złożoność czasową O((m + n) log n).
0 dla odpowiedzi nr 2
Zacznij od znalezienia wszystkich minimalnych drzew rozpinających. Następnie policz krawędzie każdego drzewa i wybierz drzewo z najmniejszą liczbą czerwonych. Chodzi o modyfikację algorytmu znajdowania minimalnych drzew rozpinających i powinieneś znaleźć przykłady.
Jeśli źle zrozumiałem pytanie i celpolega na zminimalizowaniu czerwonych krawędzi, aby znalezione drzewo rozpinające nie mogło być już minimum: zacznij od znalezienia wszystkich możliwych drzew rozpinających. Następnie wybierz drzewo z najmniejszą liczbą czerwonych krawędzi.