zoj 3659 并检查集合

http://acm.zju.edu.cn/onlinejudge/showProblem.do?

problemId=4882

现在在牡丹江，明天regional直播比赛，我会在一个月内退休。求祝福

今天做的热身赛非常紧张称号，总是错的字，晚上写写代码练练手

脑子还是不好使。没想到能够并查集

思路：题目中的操作导致的一个结果是，一条边会成为一个集合的w，---- 假设能想到这里可能就能想到并查集吧

WA了由于假设father[x]==x并不能表示x中仅仅有一个数啊。

。。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

#define ll long long

#define IN(s) freopen(s,"r",stdin)

const int MAXN = 200000+200;

struct edge{

    int u,v,w;

    bool operator < (const edge &c)const{

        return w>c.w;

    }

}e[MAXN*2];

int n,fa[MAXN],num[MAXN];

ll co[MAXN];

int Find(int x)

{

    if(x != fa[x])fa[x]=Find(fa[x]);

    return fa[x];

}

void init()

{

    for(int i=0;i<=n;i++)

        fa[i]=i,num[i]=1,co[i]=0LL;

}

void un(int x,int y,int w)

{

    int xf=Find(x);

    int yf=Find(y);

    if(xf == yf)return;

    /*if(xf == x && yf == y && num[xf]==1 && num[yf]==1)

    {

        num[xf]+=num[yf];

        fa[yf]=xf;

        co[xf]=(ll)w*num[yf]+co[xf];

        return;

    }*/

    ll cosx=(ll)w*num[yf]+co[xf];

    ll cosy=(ll)w*num[xf]+co[yf];

    if(cosx > cosy)

    {

        fa[yf]=xf;

        num[xf]+=num[yf];

        co[xf]=cosx;

        //co[y]+=w*num[x];

        return;

    }

    fa[xf]=yf;

    num[yf]+=num[xf];

    co[yf]=cosy;

}

ll solve()

{

    init();

    for(int i=1;i<n;i++)

    {

        un(e[i].u,e[i].v,e[i].w);

    }

    return co[Find(1)];

}

int main()

{

    //IN("zoj3659.txt");

    while(~scanf("%d",&n))

    {

        for(int i=1;i<n;i++)

            scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

        sort(e+1,e+n);

        printf("%I64d\n",solve());

    }

    return 0;

}