Portal
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1792 Accepted Submission(s): 883
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 107 2 16 8 34 5 85 8 22 8 96 4 52 1 58 10 57 3 77 8 810615918276
Sample Output
36131133613621613
题目大意：
给出N个点，M条无向边，以及Q个查询，每个查询询问两点间所有路径上的最大值最小值为w，并且w<=Qi的点对数。
思路：
①我们首先思考，询问两点间所有路径的最大值最小，其实就是在询问，从点u到点v最短路径上的最大值。那么希望两点间最短路径最短，其实问题就相当于求一颗MST。
对应两点间最短路的最大值，就是联通点u和点v的最后一条边的权值。
②那么我们离线处理问题，将询问按照从小到大排序，然后将每条边按照权值从小到大排序，对于当前加入树边（u，v，w），对应ans【w】=sum【u】*sum【v】，这里sum【u】表示的就是点u所在联通块点的个数。
③注意数据范围，过程维护一下即可。
Ac代码：
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
int f[1050000];
int sum[1050000];
long long int output[1050000];
struct node
{
int x,y,w;
}a[1050000];
struct node2
{
int val,pos;
}q[1050000];
int cmp(node a,node b)
{
return a.w<b.w;
}
int cmp2(node2 a,node2 b)
{
return a.val<b.val;
}
int find(int a)
{
int r=a;
while(f[r]!=r)
r=f[r];
int i=a;
int j;
while(i!=r)
{
j=f[i];
f[i]=r;
i=j;
}
return r;
}
void merge(int a,int b)
{
int A,B;
A=find(a);
B=find(b);
if(A!=B)
{
f[B]=A;
sum[A]+=sum[B];
}
}
int main()
{
int n,m,qq;
while(~scanf("%d%d%d",&n,&m,&qq))
{
for(int i=1;i<=n;i++)f[i]=i,sum[i]=1;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
}
for(int i=1;i<=qq;i++)
{
scanf("%d",&q[i].val);q[i].pos=i;
}
sort(a+1,a+1+m,cmp);
sort(q+1,q+1+qq,cmp2);
long long int ans=0;
int j=1;
for(int i=1;i<=m;i++)
{
if(find(a[i].x)!=find(a[i].y))
{
while(j<=qq&&q[j].val<a[i].w)output[q[j].pos]=ans,j++;
ans+=(long long int )sum[find(a[i].x)]*sum[find(a[i].y)];
merge(a[i].x,a[i].y);
}
}
while(j<=qq)output[q[j].pos]=ans,j++;
for(int i=1;i<=qq;i++)
{
printf("%lld\n",output[i]);
}
}
}