Cześć,
Aktualnie walczę z następującym problemem:
Mam DAG, w którym chcę obciążyć krawędzie. Mam wiele możliwości obciążania krawędzi. Dla uproszczenia załóżmy, że można je ważyć 1 lub 2.
Mam ograniczenie dla wag: Maksymalnie dwa równoległe węzły (poniżej 2,3,4 biegną równolegle) mogą mieć wagę krawędzi 1. Pozostałe muszą mieć wagę 2. Na koniec sumowane są wagi wszystkich ścieżek i przyjmuje się maksimum (powinno być jak najniższe).
Na przykład: 1 / |2 3 4 | | | | 5 | \ | / 6
Węzeł 1 ma trzech następców: 2, 3 i 4 działających równolegle. Potrzebuję czegoś, co waży wykres tak, aby ograniczenie było prawdziwe. W tym przypadku możliwym rozwiązaniem jest: krawędzie 1-4 powinny mieć wagę 2. Wszystkie pozostałe krawędzie powinny mieć wagę 1.
Byłoby wspaniale, gdyby ktoś mógł pomóc. Dzięki.
Pytanie o ważenie krawędzi
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij