Rénovations d'Enfers – Épreuve régionale 2021

Niveau 6

Énoncé

Hadès souhaite rénover un de ses Donjons dans les Enfers. Un couloir contient au moins une calamité, capable de détruire des armées entières ! Le Donjon possède plusieurs salles ; les salles dont l'accès est limité à un seul couloir sont considérées comme isolées.

Chacun des chemins possède un numéro sur l'un des murs, indiquant leur difficulté (le nombre de calamités). Étant perfectionniste, Hadès voudrait que la moyenne des niveaux des chemins soit la plus petite possible. Vous ne pouvez qu'ajouter des couloirs, et seulement aux salles isolées.

On suppose que les couloirs ajoutés ne sont pas reliés à la salle permettant déjà l'accès à la salle isolée et qu'il n'y a qu'une seule calamité dans ces couloirs.

On considère aussi qu'une salle ne peut pas avoir plusieurs couloirs menant à une même salle et qu'un couloir ne boucle jamais sur une même salle. De plus, les salles isolées ne peuvent pas s'aider des couloirs nouvellement créés pour aller vers une autre salle. On ne peut pas non plus relier directement deux salles isolées.

Saurez-vous lui rendre hommage en créant un donjon des plus effroyable, satisfaisant son exigence ?

Entrée

L'entier contiendra :

  • Sur la première ligne, un entier : $N$, le nombre de salles.
  • Sur la ligne suivante, un entier : $A$, le nombre de couloirs.
  • Sur les lignes suivantes, une liste de $A$ éléments : $L$, la liste des arcs et leur poids.
    • Une ligne par élément de la liste : une liste de $3$ entiers séparés par des espaces. Les $3$ entiers correspondent respectivement aux numéros des deux salles du donjons reliées par le couloir et le nombre de calamités présentes dans ce couloir.

Sortie

Sur chaque ligne, deux entiers séparés par des espaces représentant les numéros des salles reliées par les couloirs nouvellement créés.

NB : Plusieurs solutions peuvent être possibles. Il ne faut afficher qu'une seule d'entre elles. On suppose également qu'il existe toujours une solution.

Contraintes

  • $5 \le N \le 30$
  • $N \le A \le N \times 3$

Contraintes de performance

  • $5 \le N \le 50$
  • $N \le A \le N \times 2$

Contraintes d'exécution

Utilisation mémoire maximum
1000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
6
7
0 1 1
1 2 2
1 3 1
2 3 2
2 4 1
4 5 2
5 3 3
Exemple de sortie
0 2
ou
2 0
Commentaire

La seule salle isolée est la salle 0.

En créant un couloir de la salle 0 à la salle 2, la moyenne du nombre de calamités pour aller d'une salle à une autre est de 8.66 ce qui est le minimum possible.

Exemple d'entrée
5
5
0 1 1
1 2 1
1 4 1
1 3 1
3 4 1
Exemple de sortie
0 4
2 4
ou
0 3
2 3
ou
2 3
0 4
etc.
Commentaire

Les salles 0 et 2 sont isolées.

Le donjon montrant une symétrie, on peut créer des couloirs entre les salles isolées et les salles 3 ou 4. Ainsi le nombre moyen de calamités entre deux salles diminue à 4.96 contre 5.2 normalement.