http://acm.hdu.edu.cn/showproblem.php?pid=3938
Portal
Problem Description
ZLGG found a magic theory that the bigger banana the bigger banana peel .This important theory can help him make a portal in our universal. Unfortunately, making a pair of portals will cost min{T} energies. T in a path between point V and point U is the length of the longest edge in the path. There may be lots of paths between two points. Now ZLGG owned L energies and he want to know how many kind of path he could make.
Input
There are multiple test cases. The first line of input contains three integer N, M and Q (1 < N ≤ 10,000, 0 < M ≤ 50,000, 0 < Q ≤ 10,000). N is the number of points, M is the number of edges and Q is the number of queries. Each of the next M lines contains three integers a, b, and c (1 ≤ a, b ≤ N, 0 ≤ c ≤ 10^8) describing an edge connecting the point a and b with cost c. Each of the following Q lines contain a single integer L (0 ≤ L ≤ 10^8).
Output
Output the answer to each query on a separate line.
Sample Input
10 10 10
7 2 1
6 8 3
4 5 8
5 8 2
2 8 9
6 4 5
2 1 5
8 10 5
7 3 7
7 8 8
10
6
1
5
9
1
8
2
7
6
Sample Output
36
13
1
13
36
1
3
6
2
16
13
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 10005
#define M 50005
/*
因为询问比较多，所以需要离线
在线的意思就是每一个询问单独处理复杂度O（多少多少)，
离线是指将所有的可能的询问先一次都处理出来，
最后对于每个询问O(1)回答 对于每个询问有一个长度L，问有多少条路径的长度<=L
而且该路径的长度是T，T是从u到v上最长的边
只要求得有多少个点对使得点对之间的最大的边小于L即可。 先从小到大排序一遍询问的边的长度L，从小到大枚举u->v之间的边的长度
如果两个集合没有联通，那么联通之后路径的条数为sum[x]*sum[y]
因为长的L必定包含了短的L的答案，所以要累加起来
*/
int fa[N],sum[N]; struct node1
{
int id,ans,l;
}query[N]; struct node2
{
int u,v,len;
}edge[M]; bool cmp1(node2 a,node2 b)
{
return a.len<b.len;
} bool cmp2(node1 a,node1 b)
{
return a.id<b.id;
} bool cmp3(node1 a,node1 b)
{
return a.l<b.l;
} int Find(int x)
{
if(x==fa[x]) return x;
return fa[x]=Find(fa[x]);
} int Merge(int x,int y)
{
int fx=Find(x),fy=Find(y);
if(fx==fy) return ;
int tmp;
if(fx<fy){
fa[fy]=fx;
tmp=sum[fx]*sum[fy];
sum[fx]+=sum[fy];
}
else{
fa[fx]=fy;
tmp=sum[fx]*sum[fy];
sum[fy]+=sum[fx];
}
return tmp;
} int main()
{
int n,m,q;
while(~scanf("%d%d%d",&n,&m,&q)){
for(int i=;i<=n;i++){
fa[i]=i;
sum[i]=;
}
for(int i=;i<m;i++){
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].len);
}
for(int i=;i<q;i++){
scanf("%d",&query[i].l);
query[i].id=i;
query[i].ans=;
}
sort(edge,edge+m,cmp1);
sort(query,query+q,cmp3);
int cnt=;
for(int i=;i<q;i++){
while(edge[cnt].len<=query[i].l&&cnt<m){
int x=edge[cnt].u;
int y=edge[cnt].v;
int fx=Find(x);
int fy=Find(y);
if(fx==fy) cnt++;
else{
query[i].ans+=Merge(x,y);
cnt++;
}
}
if(i>) query[i].ans+=query[i-].ans;
}
sort(query,query+q,cmp2);
for(int i=;i<q;i++){
printf("%d\n",query[i].ans);
}
}
return ;
}