人活系列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。

演示样例输入

演示样例输出

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");

    }

}