Portal
題目鏈接：Click Here~
題目分析：
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.
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).
題目有點難看懂，一開始看不懂什麼意思。後來才知道，告訴你兩個頂點u和v.然後，這兩個點之間的花費是這兩個點中最長距離路的大小。然後，每次會給你一個能力值，叫你求出在能量范圍內的路徑方法數。
算法分析：
並查集+離線。
這道題，不是我自己想出來的。是看了別人的解體報告才知道做法的。雖然以前有用過離線的做法，但是我沒有想到聯系到這道題上。為什麼可以用到離線呢？因為我們知道小能量的范圍一定可以滿足大能量的要求。所以，我們可以從小到大的求出，在離線輸出。
#include
#include
#include
#include
using namespace std;
const int maxn = 1e4 + 5;
int f[maxn],rank[maxn],ans[maxn];
void Init()
{
for(int i = 0;i < maxn;++i)
f[i] = i,rank[i] = 1;
}
struct Node{
int from,to,val;
bool operator<(const Node& a)const{
return val < a.val;
}
}node[5*maxn];
struct Point{
int id,L;
bool operator<(const Point& a)const{
return L < a.L;
}
}p[maxn];
int Find(int x)
{
if(x == f[x])
return f[x];
return f[x] = Find(f[x]);
}
int Union(int u,int v)
{
int a = Find(u),b = Find(v);
if(a == b)return 0;
int tmp = rank[a]*rank[b];
rank[a] += rank[b];
f[b] = a;
return tmp;
}
int main()
{
int n,m,q;
while(~scanf("%d%d%d",&n,&m,&q))
{
for(int i = 0;i < m;++i)
scanf("%d%d%d",&node[i].from,&node[i].to,&node[i].val);
for(int i = 0;i < q;++i){
scanf("%d",&p[i].L);
p[i].id = i;
}
sort(node,node+m);
sort(p,p+q);
Init();
int j = 0,cnt = 0;
for(int i = 0;i < q;++i){
while(j
