首页 > 代码库 > 人活着系列之Streetlights (克鲁斯卡尔)
人活着系列之Streetlights (克鲁斯卡尔)
人活着系列之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 3 0 1 1 1 2 5 0 2 2 4 3 0 1 1 1 2 3 0 2 4
示例输出
5 -1
提示
水题
#include<iostream> #include<cstdio> #include<cstring> #include <cstdlib> #include <math.h> #include <algorithm> #define INF 0x3f3f3f3f const int N = 100010; using namespace std; struct node { int u,v,w; } g[N]; int num = 0,sum = 0,zong = 0,n,m,father[N]; int cmp(const void *a,const void *b) { struct node *X,*Y; X = (struct node *)a; Y = (struct node *)b; return X->w - Y->w; } int findx(int r) { while(r != father[r]) { r = father[r]; } int i = r,j; while(father[i] != r) { j = father[i]; father[i] = r; i = j; } return r; } void Kruskal() { for(int i = 0; i < m; i++) { int uu = findx(g[i].u); int vv = findx(g[i].v); if(uu!=vv) { num ++; sum += g[i].w; father[uu] = vv; } if(num == n-1) break; } } void init() { zong = 0,num = 0,sum = 0; for(int i = 0; i <=n; i++) father[i] = i; } int main() { while(~scanf("%d%d",&n,&m)) { init(); for(int i = 0; i < m; i++) { scanf("%d%d%d",&g[i].u,&g[i].v,&g[i].w); zong += g[i].w; } qsort(g,m,sizeof(g[0]),cmp); Kruskal(); (num==n-1)?printf("%d\n",zong-sum):puts("-1"); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。