Optymalizacja zadania grafowego

pytanie zadane 5 września 2020 w Algorytmy przez wojtek_suchy Mądrala (6,880 p.)

Cześć mam takie zadanie:

Bajtocja

Limit pamięci: 32 MB

Za górami, za lasami, za rzekami, za morzami leży kraj potężny i bogaty zwany Bajtocją. Panuje tam dobrotliwy król Bajtazar I Wielki, słynny ze swej troski o infrastrukturę kraju. W Bajtocji znajduje się miast. Władca rozkazał swym nadwornym architektom przygotować projekty nowych ponaddźwiękowych traktów konnych. Jako odpowiedź otrzymał propozycji, każda z nich składa się z trzech liczb , , , gdzie i są miastami końcowymi traktu (trakt łączy te miasta bezpośrednio i nie przebiega przez inne miasta), a oznacza koszt zbudowania tego traktu. Każdym traktem można podróżować zarówno z miasta do , jak i w stronę przeciwną. Zamierzeniem króla jest budowa sieci traktów w taki sposób, aby można było nimi przejechać między każdymi dwoma miastami, być może odwiedzając po drodze inne miejscowości. Bajtazar jest bardzo oszczędnym królem, więc postanowił zgodzić się tylko na taką sieć, która będzie możliwie najtańsza.

Zadanie

Opracuj program, który:

wczyta ze standardowego liczbę miast, liczbę proponowanych traktów oraz opisy tych traktów,
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,
wypisze na standardowe wyjście zestawienie uzyskanych wyników.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite: liczbę miast i liczbę proponowanych traktów , rozdzielone pojedynczą spacją i spełniające warunki , . Każdy z kolejnych wierszy zawiera po trzy liczby całkowite , , rozdzielone pojedynczymi spacjami, opisujące proponowany trakt, przy czym i oznaczają miasta będące końcami traktu, zaś jest ceną budowy tego traktu (, ).

Wyjście

W każdym z kolejnych wierszy należy wypisać słowo "TAK" albo "NIE", w zależności od tego, czy można skonstruować plan budowy zgodny z życzeniem króla, dla którego trakt opisany w odpowiednim wierszu jest w nim zawarty. Możesz bezpiecznie założyć, że dla danych wejściowych zawsze istnieje plan budowy spełniający wymogi Bajtazara.

Przykład

Dla danych wejściowych:

poprawną odpowiedzią jest:

TAK
TAK
TAK
NIE
TAK
NIE
TAK
TAK
TAK
TAK

No i napisałem taki kod:

#include <bits/stdc++.h>

using namespace std;

struct trakt{
    int p;
    int k;
    int w;
};

bool bfs(vector<vector<pair<int, int>>> & graf, int limit, int p, int k){
    queue<int> kolejka;
    vector<bool> seen(graf.size());
    for (pair<int, int> next_node : graf[p]){
        if (next_node.first != k && next_node.second < limit){
            kolejka.push(next_node.first);
            seen[next_node.first] = true;
        }

    }
    int curr_node;
    while (kolejka.size() > 0){
        curr_node = kolejka.front();
        kolejka.pop();
        for (pair<int, int> next_node : graf[curr_node]){
            if (next_node.second < limit && seen[next_node.first] == false){
                if (next_node.first == k)
                    return false;
                kolejka.push(next_node.first);
                seen[next_node.first] = true;
            }
        }
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> graf(n+1);
    vector<trakt> trakty(m);
    for (int i = 0; i < m; i++){
        cin >> trakty[i].p >> trakty[i].k >> trakty[i].w;
        graf[trakty[i].p].push_back(make_pair(trakty[i].k, trakty[i].w));
        graf[trakty[i].k].push_back(make_pair(trakty[i].p, trakty[i].w));
    }

    for (trakt curr_trakt : trakty){
        if (bfs(graf, curr_trakt.w, curr_trakt.p, curr_trakt.k))
            cout << "TAK\n";
        else
            cout << "NIE\n";
    }



  return 0;
}

Niestety mój algorytm jest stanowczo za wolny, nie przewidziałem też że tą samą drogę można "nadpisać" tzn np podać trakt 9 2 4 a później 9 2 16 (mój algorytm zmieniłby wagę krawędzi na 16 co oczywiście jest błędne ale poprawianie tego błędu tylko spowolniłoby mój algorytm który jest zbyt wolny) Czy macie jakieś pomysły jak zrobić to zadnie szybciej?

1 odpowiedź

odpowiedź 5 września 2020 przez Whistleroosh Maniak (56,980 p.)

W tym zadaniu potrzebne jest minimalne drzewo rozpinające (po angielsku MST). Trzeba zauważyć, że dowolne MST spełnia warunki zadania, gdyż z każdego wierzchołka można dojść do każdego innego, a także koszt stworzenia takiego drzewa jest minimalny. Więc stwórzmy jakieś MST np. algorytmem Kruskala. Teraz dla każdego traktu mamy dwie możliwości:

1) trakt należy już do MST, więc odpowiedź dla niego to "TAK"

2) trakt nie należy do MST, czyli tworzy jakiś cykl w naszym MST

Punkt pierwszy mamy już rozwiązany, teraz tylko pytanie co z drugim punktem. Tutaj potrzebne jest proste spostrzeżenie, że jeżeli po dodaniu traktu w MST powstał cykl, wystarczy usunąć inny trakt, który leży na tym cyklu, aby z powrotem otrzymać poprawne MST bez cykli. Tylko pytanie który trakt należy usunąć? Odpowiedź jest prosta. Jeżeli dodaliśmy trakt o koszcie c i utworzył on cykl, to musimy usunąć inny trakt, który leży na tym samym cykl i który też kosztował c. Gdybyśmy usunęli trakt o koszcie mniejszym niż c, to wtedy otrzymane drzewo nie byłoby MST. Dodatkowo na cyklu nie może znajdować się trakt o koszcie większym niż c, gdyż oznaczałoby to, że aktualne drzwo nie jest MST.

Więc to co trzeba zrobić w tym zadaniu, to utworzyć dowolne MST. Jeżeli krawędź należy do MST, to odpowiedź dla niej to "TAK". Jeżeli krawędź nie należy do MST, to należy sprawdzić, czy na cyklu, który zostanie przez nią utworzony, znajduje się inny trakt o tym samym koszcie. Jeżeli taki trakt znajdziemy, to odpowiedzią jest "TAK", a w przeciwnym wypadku "NIE.

komentarz 5 września 2020 przez Whistleroosh Maniak (56,980 p.)

Powiem jeszcze trochę o tym jak szybko znaleźć trakt o koszcie c na cyklu. Pierwszy sposób jest taki, że jeżeli do drzewa MST dodajmy krawędź między wierzchołkami x i y o koszcie c, to wystarczy sprawdzić, czy największa wartość w drzewie MST na ścieżce od x do LCA(x, y) a także na ścieżce od y do LCA(x, y) jest równa c (LCA to oczywiście najmniejszy wspólny przodek). Wynika to z tego, że wiemy, iż na cyklu utworzonym przez krawędź (x, y) nie może być wartości większej niż c.