L'Atelier Monstre

YellowStar doit préparer un examen d'anglais dans trois semaiens et a besoin de mémoriser n mots, chacun de longueur m. Il utilise une méthode de mémorisation par association. Pour mémoriser un nouveau mot T : Si YellowStar mémorise le mot sans aucune aide, il consomme une énergie égale à la longueur du mot m. S'il utilise un mot déjà mémorisé ...

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 rec ...

0x61 Chemins les plus courts Algorithmes source unique Algorithme de Dijkstra : Pour un graphe avec des poids d'arêtes non négatifs, cet algorithme calcule les distances les plus courtes depuis un sommet source. Il fonctionne par sélection gloutonne : à chaque itération, le sommet non visité avec la distance la plus faible est choisi, puis on m ...

Contrôle des Composantes Connexes avec l'Algorithme de Kruskal L'algorithme de Kruskal est traditionnellement utilisé pour trouver l'arbre couvrant de poids minimum (ACPM) complet. Cependant, en modifiant la condition d'arrêt, il devient un outil puissant pour les problèmes de regroupement spatial (clustering). Si l'objectif est de partitionner ...