Responsive image

问题 2376 --最优灌溉

2376: 最优灌溉

时间限制: 1 Sec  内存限制: 256 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

雷雷承包了很多片麦田，为了灌溉这些麦田，雷雷在第一个麦田挖了一口很深的水井，所有的麦田都从这口井来引水灌溉。
为了灌溉，雷雷需要建立一些水渠，以连接水井和麦田，雷雷也可以利用部分麦田作为“中转站”，利用水渠连接不同的麦田，这样只要一片麦田能被灌溉，则与其连接的麦田也能被灌溉。
现在雷雷知道哪些麦田之间可以建设水渠和建设每个水渠所需要的费用（注意不是所有麦田之间都可以建立水渠）。请问灌溉所有麦田最少需要多少费用来修建水渠。

输入描述

输入的第一行包含两个正整数 n,m，分别表示麦田的片数和雷雷可以建立的水渠的数量。麦田使用 1,2,3,…… 依次标号。
接下来 m 行，每行包含三个整数 ai,bi,ci，表示第 ai 片麦田与第 bi 片麦田之间可以建立一条水渠，所需要的费用为 ci。

输出描述

输出一行，包含一个整数，表示灌溉所有麦田所需要的最小费用。

样例输入

4 4
1 2 1
2 3 4
2 4 2
3 4 3

样例输出

6

提示

前 20% 的评测用例满足：n≤5。

前 40% 的评测用例满足：n≤20。

前 60% 的评测用例满足：n≤100。

所有评测用例都满足：1≤n≤1000，1≤m≤100,000，0≤ci≤10,000。

保证一定可以灌溉到所有麦田，并且无重边和自环

来源

20大数据吴镓壮 最小生成树 

[提交][状态]
ACM算法攻关部