L'Atelier Monstre

Problème T1 : Arbre couvrant minimum avec poids conditionnel Énoncé : Soit un graphe G. On doit trouver un arbre couvrant minimum dont le poids est défini ainsi : si le poids maximal des arêtes w_max ≤ k, alors le poids est k - w_max ; sinon, le poids est la somme des |w_i - k| pour toutes les arêtes avec w_i ≥ k. Analyse : Les cas spéciaux où ...