http://acm.hdu.edu.cn/showproblem.php?pid=5441
Travel
Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 2061 Accepted Submission(s): 711
For each test case, the first line consists of three integers n,m and q where n≤20000,m≤100000,q≤5000. The Undirected Kingdom has n cities and mbidirectional roads, and there are q queries.
Each of the following m lines consists of three integers a,b and d where a,b∈{1,...,n} and d≤100000. It takes Jack d minutes to travel from city a to city band vice versa.
Then q lines follow. Each of them is a query consisting of an integer x where x is the time limit before Jack goes berserk.
Note that (a,b) and (b,a) are counted as different pairs and a and b must be different cities.
题意：是有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 struct node
{
int u, v, w, index;
} a[N], b[N]; int r[N], f[N], Q[N]; int cmp(node n1, node n2)
{
return n1.w < n2.w;
} int Find(int x)
{
if(x!=f[x])
f[x]=Find(f[x]);
return f[x];
} int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int n, m, q, i;
scanf("%d%d%d", &n, &m, &q); for(i=; i<=n; i++)
{
f[i] = i;
r[i] = ;
} for(i=; i<m; i++)
scanf("%d%d%d", &a[i].u, &a[i].v, &a[i].w);
for(i=; i<q; i++)
{
scanf("%d", &b[i].w);
b[i].index = i;
} sort(a, a+m, cmp);
sort(b, b+q, cmp); int sum = , j = ;
for(i=; i<q; i++)
{
while(j<m && a[j].w<=b[i].w)
{
int fu = Find(a[j].u);
int fv = Find(a[j].v); if(fu!=fv)
{
f[fu] = fv;
sum += r[fu]*r[fv]; ///两个集合的任意组合
r[fv] += r[fu]; ///r[i]代表i的根节点所包含的元素的个数
}
j++;
}
Q[b[i].index] = sum*; ///ab和ba是不一样的
} for(i=; i<q; i++)
printf("%d\n", Q[i]);
}
return ;
}