人活系列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");
}
}


版权声明:本文博客原创文章。博客,未经同意,不得转载。

上一篇:php5.4安装fileinfo扩展


下一篇:[Training Video - 3] [Java Introduction] [Object Oriented Programming]