HDOJ5441(图论中的并查集)

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAX_N=;

const int MAX_V=;

const int MAX_Q=;

struct edge{

    int from,to,cost;

}es[MAX_N];

int V,E,Q;

bool comp(const edge &e1,const edge &e2)

{

    return e1.cost < e2.cost;

}

void getMap()

{

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

    {

        scanf("%d %d %d",&es[i].from,&es[i].to,&es[i].cost);

    }

    sort(es,es+E,comp);

}

int par[MAX_V];

int nodes[MAX_V];

void Init()

{

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

    {

        par[i]=i;

        nodes[i]=;

    }

}

int Find(int x)

{

    if(par[x]==x)

        return x;

    return par[x]=Find(par[x]);

}

struct Query{

    int limit;

    int index;

}query[MAX_Q];

bool comp1(Query q1,Query q2)

{

    return q1.limit < q2.limit;

}

long long ans[MAX_Q];

void Solve()

{

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

    {

        scanf("%d",&query[i].limit);

        query[i].index=i;

    }

    sort(query,query+Q,comp1);

    long long sum=;

    int j=;

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

    {

        while(j<E&&query[i].limit>=es[j].cost)

        {

            int u=Find(es[j].from);

            int v=Find(es[j].to);

            if(u!=v)

            {

                sum+=*nodes[u]*nodes[v];

                par[u]=v;// 将u,v两集合合并,v为祖先

                nodes[v]+=nodes[u];

            }

            j++;

        }

        ans[query[i].index]=sum;

    }

    // 优化时间,将query全部输入之后再集体输出

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

    {

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

    }

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d %d %d",&V,&E,&Q);

        getMap();

        Init();

        Solve();

    }

    return ;

}