hdu5441 并查集+克鲁斯卡尔算法

这题计算 一张图上 能走的 点对有多少个  对于每个限制边权 ， 对每条边排序，对每个查询排序

然后边做克鲁斯卡尔算法 的时候变计算就好了

#include <iostream>

#include <algorithm>

#include <string.h>

#include <cstdio>

#include <vector>

#include <queue>

using namespace std;

const int maxn=;

typedef long long LL;

struct edg{

   int a,b,d;

   edg(int ca=,int cb=,int cd=)

   {

        a=ca; b=cb; d=cd;

   }

   bool operator <(const edg &rhs)const{

      return d<rhs.d;

   }

}E[];

struct query{

   LL id,d;

   query(LL cid=, LL cd= ){

       id=cid; d=cd;

   }

   bool operator <(const query &rhs)const {

       return d<rhs.d;

   }

}Q[];

LL S[maxn];

LL num[maxn];

int fa[maxn];

int fin(int a)

{

     return fa[a]=(fa[a]==a)?a:fin(fa[a]);

}

LL ans[];

int main()

{

    int cas;

    scanf("%d",&cas);

    for(int cc=; cc<=cas; cc++)

        {

             int n,m,q;

             scanf("%d%d%d",&n,&m,&q);

             for(int i=; i<m; i++)scanf("%d%d%d",&E[i].a,&E[i].b,&E[i].d);

             for(int i=; i<=n; i++){fa[i]=i;S[i]=;num[i]=;}

             for(int i=; i<q; i++) {scanf("%I64d",&Q[i].d);Q[i].id=i; ans[i]=;}

             sort(E,E+m);

             sort(Q,Q+q);

             int loc=;

             LL D=;

             for(int i=; i<q; i++)

                {

                    while(loc<m&&E[loc].d<=Q[i].d){

                        int a=E[loc].a,b=E[loc].b;

                        a=fin(a);

                        b=fin(b);

                        if(a==b){ loc++; continue; }

                        D=D-S[a]-S[b];

                        fa[b]=a;

                        num[a]+=num[b];

                        S[a]=1LL*num[a]*(num[a]-);

                        D=D+S[a];

                        loc++;

                    }

                   ans[Q[i].id]=D;

                }

                for(int i=; i<q; i++)

                    printf("%I64d\n",ans[i]);

        }

    return ;

}