Online
Problema cere costul arborelui partial de cost minim, graful initial schimbandu-se la fiecare pas. Prima idee ar fi rularea unui algoritm clasic pentru gasirea arborelui partial de cost minim de K + 1 ori. In functie de algoritmul folosit si de metoda de implementare, obtinem complexitati diferite. Folosind algoritmul Kruskal putem obtine complexitati de O(K * N * M), O(K * (M * log M + N2)) sau O(K * M * log M). Folosind algoritmul Prim putem obtine complexitatea O(K * N2), sau O(K * M * log N) in cazul folosirii heap-urilor la implementare.
Totusi niciuna dintre aceste variante nu se incadreaza in timp pentru limitele date, asa ca propunem urmatorul algoritm, avand complexitatea O(N2 + K * N). Prima data se gaseste arborele partial de cost minim pentru graful initial, folosind algoritmul Prim. Pentru urmatorii K pasi avem doua posibilitati:
- Muchia curenta este intre doua noduri din arborele partial minim actual. Daca muchia are lungime mai mica, suprascriem muchia din arbore si costul arborelui se imbunatateste cu diferenta costurilor. Daca muchia are lungime mai mare sau egala, arborele ramane neschimbat.
- Muchia nu face parte din arbore. Fiindca arborele are numar maxim de muchii din punctul de vedere al aciclitatii, o noua muchie va forma cu siguranta un ciclu. Pentru a ajunge iarasi la un arbore, din acest ciclu trebuie stearsa o muchie. Pentru ca arborele care rezulta sa aiba cost minim, vom sterge muchia cu cost maxim din ciclu.
