c++这道题怎么做?
题目描述众所周知,梁老师家的狗豆豆,特别喜欢在电线杆底下撒尿。在梁老师家周围,有n个电线杆,其中有m对电线杆中间有路相连,每条路有一个正整数的长度值w,于是周围的地图变成...
题目描述众所周知,梁老师家的狗豆豆,特别喜欢在电线杆底下撒尿。在梁老师家周围,有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
展开
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询