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