Fondamentaux et Template

L'implémentation classique de l'algorithme de Kruskal repose sur deux piliers : le tri des arêtes par poids et la gestion des composantes connexes via une structure Union-Find (Disjoint Set Union - DSU). Pour des problèmes compétitifs exigeants, il est crucial d'optimiser ces opérations.

Premièrement, la fonction de recherche de racine avec compression de chemin :

int getRepresentative(int node) {
    if (dsu[node] == node) return node;
    return dsu[node] = getRepresentative(dsu[node]);
}

Ensuite, l'union de deux ensembles :

void unionSets(int u, int v) {
    int rootU = getRepresentative(u);
    int rootV = getRepresentative(v);
    if (rootU != rootV) dsu[rootU] = rootV;
}

La procédure principale trie les arêtes et construit progressivement l'arbre couvrant minimal (ACM ou MST) :

long long computeMST(vector<Edge>& edges, int n) {
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });
    
    for (int i = 1; i <= n; ++i) dsu[i] = i;
    long long totalWeight = 0;
    int edgesCount = 0;
    
    for (const auto& e : edges) {
        if (getRepresentative(e.u) != getRepresentative(e.v)) {
            unionSets(e.u, e.v);
            totalWeight += e.weight;
            edgesCount++;
        }
    }
    return (edgesCount == n - 1) ? totalWeight : -1; // Vérification de connectivité
}

Bissection sur la Réponse avec Contraintes

Certains problèmes imposent des contraintes spécifiques sur les types d'arêtes utilisées. Par exemple, minimiser le coût maximal tout en garantissant qu'un nombre $k$ d'arêtes d'un type spécifique sont incluses. La stratégie consiste à utiliser une bissection (recherche dichotomique) sur le coût admissible.

Dans la fonction de vérification check(maxCost), on ne considère que les arêtes dont le poids est inférieur ou égal au seuil testé. On privilégie ensuite l'ajout des arêtes du type prioritaire pour atteindre le quota $k$, avant de combler le reste avec les autres types pour assurer la connectivité totale.

bool verify(int limit, const vector<EdgeWithClass>& allEdges, int nodes, int kReq) {
    vector<int> parent(nodes + 1);
    iota(parent.begin(), parent.end(), 0);
    
    auto find = [&](int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    };
    
    auto unite = [&](int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx != ry) parent[ry] = rx;
    };
    
    // Passer 1 : Préférence aux arêtes spéciales
    int countSpecial = 0;
    int connectedComp = nodes;
    
    for (const auto& e : allEdges) {
        if (e.cost > limit || e.type != SPECIAL_TYPE) continue;
        if (find(e.u) != find(e.v)) {
            unite(e.u, e.v);
            countSpecial++;
            connectedComp--;
        }
    }
    
    // Passer 2 : Compléter avec les arêtes standards si nécessaire
    if (countSpecial >= kReq && connectedComp == 1) return true;
    
    // Si on n'a pas assez d'arêtes spéciales mais qu'on peut encore former l'arbre
    // Logique simplifiée : on permet d'utiliser des normales pour connecter
    
    return false; 
}</int>

L'itération de la bissection s'effectue alors sur la plage des poids possibles :

int low = 0, high = MAX_WEIGHT;
while (low < high) {
    int mid = low + (high - low) / 2;
    if (verify(mid, edges, N, K)) high = mid;
    else low = mid + 1;
}
cout << low << endl;

Comptage des Arbres Couvrants Minimaux

Lorsque plusieurs configurations d'arêtes produisent le même poids total minimal, compter ces variantes fait appel au théorème matriciel-tree. Cependant, appliquer directement ce théorème sur le graphe complet est inexact si les poids varient. Il faut regrouper les calculs par classes de poids équivalentes.

La méthode consiste à :

1. Identifier tous les groupes d'arêtes ayant le même poids.
2. Traiter chaque groupe séquentiellement dans l'ordre croissant des poids.
3. Pour un groupe donné, contracter les composants déjà connectés par les poids inférieurs (en utilisant DSU).
4. Construire la matrice de Laplacienne sur les sommets du graphe réduit (après contraction) contenant uniquement les arêtes du groupe actuel.
5. Calculer le déterminant mineur principal de cette matrice via l'élimination de Gauss.

Le résultat final est le produit des déterminants obtenus à chaque étape.

Deuxième Meilleur Arbre Couvrant (Strictement)

Pour trouver l'arbre dont le poids est strictement supérieur au minimum global mais minimal par ailleurs, on procède par énumération d'une arête non utilisée. Pour chaque telle arête $(u, v)$ ajoutée, un cycle est créé. Pour rétablir la propriété d'arbre, il faut retirer la plus grande arête existante sur le cycle formé.

Si le poids de cette arête retirée est strictement inférieur au nouveau poids ajouté, nous avons trouvé un candidat valide. Le défi technique réside dans la recherche rapide de l'arête maximale sur le chemin unique entre $u$ et $v$ dans l'arbre initial.

Ceci se résout efficacement grâce à l'algorithme de Lowest Common Ancestor (LCA) combiné au saut binomial (binary lifting). Durant le précalcul de profondeur et de tables de sauts, on stocke aussi la valeur maximale et la sous-maximale rencontrée sur le chemin vers l'ancêtre direct.

// Structure de données pour le lifting
long long up[MAXN][LOG];
long long maxVal[MAXN][LOG];
long long subMaxVal[MAXN][LOG];

void dfs(int u, int p, long long w) {
    up[u][0] = p;
    maxVal[u][0] = w;
    subMaxVal[u][0] = -INF;
    
    for (int k = 1; k < LOG; ++k) {
        up[u][k] = up[up[u][k-1]][k-1];
        // Fusion des valeurs maximales/submaximales sur le segment combiné
        long long vals[] = {maxVal[u][k-1], maxVal[up[u][k-1]][k-1],
                            subMaxVal[u][k-1], subMaxVal[up[u][k-1]][k-1]};
        sort(vals, vals+4);
        maxVal[u][k] = vals[3];
        subMaxVal[u][k] = (vals[2] == vals[3]) ? vals[1] : vals[2];
    }
    
    for(auto& edge : adj[u]) if(edge.to != p)
        dfs(edge.to, u, edge.w);
}

Variations basées sur les Propriétés Mathématiques

Certaines instances de problèmes définissent le poids d'une arête de manière non standard, nécesistant une adaptation stratégique :

• Fonctions de distance additivse : Si le coût d'une arête est la somme des coûts des sommets ($C_{uv} = V_u + V_v$), la meilleure stratégie consiste à connecter les sommets coûteux à celui qui possède la valeur minimale globale, créant une topologie en étoile implicite.
• Systèmes multiplexe : Dans des graphes où le coût dépend des facteurs premiers (ex: différence entre LCM et GCD), une approche par criblage et DSU permet de construire l'ACM sans générer toutes les arêtes explicites. On privilégie les connexions avec les nombres premiers présents dans l'intervalle.
• Chemin critique modifié : Si l'objectif est de minimiser la somme des deux plus grandes arêtes sur un chemin simple, une variante de l'algorithme de Dijkstra tenant compte des deux plus grands poids historiques permet de résoudre le problème en temps linéaire logarithmique.