Question

c++这道题怎么做？

题目描述众所周知，梁老师家的狗豆豆，特别喜欢在电线杆底下撒尿。在梁老师家周围，有n个电线杆，其中有m对电线杆中间有路相连，每条路有一个正整数的长度值w，于是周围的地图变成了一个n个点m条边组成的带权无向图。现在梁老师打算遛狗，在路上遛狗是需要收费的，梁老师很穷，只能付费购买不超过k条路的遛狗权。现在梁老师想从m条路中挑选不超过k条路，使得路的长度之和加起来最大。但是豆豆是个路痴，如果选择的路构成了环，它就有可能会迷路走不回家。所以梁老师希望选择的路不能构成环。请你帮梁老师计算出，它能选择的路的长度之和最大是多少。输入格式第一行包含三个正整数 n、m、k。分别表示电线杆的数量，电线杆之间路的数量，以及能购买的最多的路的数量。接下来 m 行中每行包含三个正整数 u、v、w。表示u到v这两个电线杆之间的路的长度是w。输出格式只包含一个正整数，表示这能选出的路的长度和的最大值。输入输出样例输入 #1复制5 4 31 2 101 3 92 3 74 5 3输出 #1复制22

Answer 1

豆豆说：今天不出去。