Ελάχιστο συνδετικό δέντρο (Kruskal)
Ταξινομείς τις ακμές κατά βάρος και κρατάς όσες ενώνουν δύο διαφορετικές συνιστώσες. , με DSU.
Πότε
Θέλεις να συνδέσεις όλες τις κορυφές με το ελάχιστο συνολικό κόστος. Ή, συχνότερα στους διαγωνισμούς, θέλεις μια ιδιότητα του MST: «ποιο είναι το μέγιστο βάρος που πρέπει να διασχίσεις για να πας από το στο , στην καλύτερη περίπτωση;» Η απάντηση είναι η βαρύτερη ακμή στο μονοπάτι του MST.
Η ιδέα
Ιδιότητα τομής: για κάθε διαμέριση των κορυφών σε δύο μέρη, η ελαφρύτερη ακμή που τα συνδέει ανήκει σε κάποιο MST. Ο Kruskal την εφαρμόζει άπληστα. Περνάει τις ακμές από την ελαφρύτερη. Όταν μια ακμή ενώνει δύο συνιστώσες, είναι η ελαφρύτερη που διασχίζει την τομή «αυτή η συνιστώσα / όλα τα άλλα», άρα την κρατάμε. Αν οι άκρες της είναι ήδη στην ίδια συνιστώσα, θα έκλεινε κύκλο, άρα την πετάμε.
Ο κώδικας χρειάζεται τη DSU. Αν ο γράφος δεν είναι συνεκτικός, επιστρέφει το βάρος ενός ελάχιστου συνδετικού δάσους. Για να ξέρεις αν υπάρχει δέντρο, μέτρα τις ακμές που κράτησες: πρέπει να είναι .
Παγίδες
- Στο
Road Reparationη απάντηση είναιIMPOSSIBLEόταν ο γράφος δεν είναι συνεκτικός. Αυτό είναι το «μέτρα τις ακμές» πιο πάνω. - Τα βάρη αθροίζονται σε
long long: ακμές επί .
Κώδικας
Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.
// Minimum spanning tree (forest), Kruskal. O(m log m) for the sort.
// Needs dsu.cpp. Edges in increasing weight; keep an edge when it joins two components.
// Returns the total weight; if the graph is disconnected, it is the weight of a minimum spanning forest.
struct WeightedEdge {
int u;
int v;
ll w;
};
ll kruskal(int n, vector<WeightedEdge> edges, vector<WeightedEdge>* chosen = nullptr) {
sort(edges.begin(), edges.end(), [](const WeightedEdge& a, const WeightedEdge& b) {
return a.w < b.w;
});
DSU dsu(n);
ll total = 0;
for (const WeightedEdge& e : edges) {
if (dsu.unite(e.u, e.v)) {
total += e.w;
if (chosen != nullptr) {
chosen->push_back(e);
}
}
}
return total;
}
Ελέγχθηκε σε 1.000 τυχαίες περιπτώσεις απέναντι σε αργή, προφανώς σωστή λύση, με AddressSanitizer και UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).
Για εξάσκηση στο CSES
Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.
- Road Reparation · Graph Algorithms
Περισσότερα στο USACO Guide
- Minimum Spanning Trees · usaco.guide/gold/mst
Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.