本文共 891 字，大约阅读时间需要 2 分钟。

Description

有n个城市，其中有些城市之间可以修建公路，修建不同的公路费用是不同的。现在我们想知道，最少花多少钱修公路可以将所有的城市连在一起，使在任意一城市出发，可以到达其他任意的城市。

Input

输入包含多组数据，格式如下。

第一行包括两个整数n m，代表城市个数和可以修建的公路个数。(n <= 100， m <=10000)

剩下m行每行3个非负整数a b c，代表城市a 和城市b之间可以修建一条公路，代价为c（城市编号从1到n）。

Output

每组输出占一行，仅输出最小花费。

Input

3 21 2 11 3 11 0

Output

20

答案：

Kruskal：

#include 
   
    #include
    
     #define ll long long#define INF 0x3f3f3f3fconst int N = 11111;using namespace std;struct node{    int u;    int v;    int w;} p[N];int vis[N];bool cmp(node x,node y){    return x.w
     
      >n>>m)    {        init(n);        int i;        for(i=1; i<=m; i++)        {            cin>>p[i].u>>p[i].v>>p[i].w;        }        sort(p+1,p+1+m,cmp);        int ans=0;        for(i=1; i<=m; i++)        {            if(!Merge(p[i].u,p[i].v))            {                ans+=p[i].w;                //cnt++;            }        }        cout<
      
       <