Travel---hdu5441（并查集）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5441

题意：是有n个城市，m条边包含u v w；代表u到v的时间是w；

给q的时间x，求在x时间内Jack可以到达多少对城市；其中ab和ba是不同的；

1
5 5 3
2 3 6334
1 5 15724
3 5 5705
4 3 12382
1 3 21726
6000///////可以到达35和53；
10000//////2 5 3是可以相互到达的所以有6种；
13000///////2 3 5 4是想通的有12种；

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 100100

int f[20100], r[20100], Ans[5005];

struct node
{
    int u, v, w, index;
}a[N], b[5005];

int cmp(node p, node q)
{
    return p.w < q.w;
}

int Find(int x)
{
    if(x!=f[x])
        f[x] = Find(f[x]);
    return f[x];
}

int main()
{
    int T, n, m, q;

    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d%d", &n, &m, &q);

        for(int i=0; i<=n;i++)
        {
            f[i] = i;
            r[i] = 1;
        }

        for(int i=0; i<m; i++)
            scanf("%d%d%d", &a[i].u, &a[i].v, &a[i].w);

        for(int i=0; i<q; i++)
        {
            scanf("%d", &b[i].w);
            b[i].index = i;
        }

        sort(a, a+m, cmp);
        sort(b, b+q, cmp);
        
        int j=0;
        int ans = 0;
        for(int i=0; i<q; i++)
        {
            while(j<m && b[i].w>=a[j].w)///满足条件的
            {
                int pa = Find(a[j].u);
                int pb = Find(a[j].v);
                if(pa != pb)
                {
                    f[pa] = pb;
                    ans += r[pa]*r[pb];///加上两个集合的数任意组合；
                    r[pb]+=r[pa];///r[i]代表i的根节点所包含的元素个数；
                }
                j++;
            }
            Ans[b[i].index] = ans*2;///保存结果，ab和ba是不一样的；
        }
        for(int i=0; i<q; i++)
            printf("%d
", Ans[i]);
    }
    return 0;
}