人活着系列之Streetlights
Time Limit: 1000ms Memory limit: 65536K 有疑问?点这里^_^
题目描写叙述
人活着假设是为了家庭,亲情----能够说是在这个世界上最温暖人心的,也是最让人放不下的,也是我在思索这个问题最说服自己接受的答案。对。或许活着是一种责任。为了生殖下一代。为了孝敬父母。男人要养家糊口,女人要生儿育女,就这样循环的过下去。但终于呢?还是劳累愁烦。转眼成空呀!
为了响应政府节约能源的政策,某市要对路灯进行改革,已知该市有n个城镇。有m条道路。改革后该市仅仅开一部分道路的路灯。并且要使随意两个城镇之间有路灯开着。
城镇编号为0~n-1;每条道路开的路灯要花费一定的费用。求改革后最多能节省多少费用。
输入
多组输入,每组第一行输入n, m(1≤n≤ 100000,n-1≤m ≤100000);接下来m行,每行3个数u, v, w;代表城镇u到城镇v开着路灯的花费为w。
输出
输出改革后最多能节省的费用,假设数据不能保证随意两个城镇有路灯开着,输出-1。
演示样例输入
3 30 1 11 2 50 2 24 30 1 11 2 30 2 4
演示样例输出
5-1
提示
赤裸裸的最小生成树,哎 没办法。当时没学就是不会做,题意:总花费减去最小花费即为能够节省的花费。今天刚学Kruskal,说一下它的思想:如果有m条边。n个节点,最小生成树终于会从m条边中选出n-1条连通的边。而利用并查集正好能够解决连通这一问题,先把边按权值升序排好。然后每选出一条边。便把他们放到一个集合里去,终于就会砍出一条最小生成树。刚学,理解的可能不够深刻。。
#include#include #include #include #include #include #include #include #include #include #include
版权声明:本文博主原创文章,博客,未经同意不得转载。