Module: Arbres couvrants : l'algorithme de Kruskal


Problem

2 /4


Spanning Tree

Problem

Il est nécessaire de trouver un arbre couvrant de poids minimum dans un graphe connexe.
 
Entrée
La première ligne du fichier d'entrée contient deux nombres naturels n et m - le nombre de sommets et d'arêtes du graphe, respectivement (1≤n≤20000, 0≤m≤100000). Les m lignes suivantes contiennent la description des arêtes, une par ligne. Le numéro d'arête i est décrit par trois nombres naturels bi, ei et wi - les numéros des extrémités de l'arête et son poids, respectivement (1≤bi,ei≤n, 0≤wi≤100000).
 
Le graphique est connecté.
 
Sortie
Imprime un seul entier - le poids de l'arbre couvrant minimum.
 
4 4
1 2 1
2 3 2
3 4 5
4 1 4
Entrée Sortie
7

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!