Portal
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 931 Accepted Submission(s): 466
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
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
36
2
16
13
13
1
13
36
1
36
2
16
13
Source
题目意思:
给定一张无向图，要你求出满足小于或等于给定边长的最多边长的种类数目。当然关键是有n次询问。
思路：
对于一颗有n条路径的无向图，可以知道，当与另一个m条路径的无向图合并为一个全新的无向图时： 此时的路径为 n*m;
当然这题的重点不在这里，此题关键是有q次询问，对于每一次询问，若我们都去重新求解一次，将会很花时间，无疑TLE倒哭。%>_<%
于是采用离线处理（这里是开了解题报告才想起来，这么巧妙的地方，果然是too yong 哇！ ）：
离线的思路为： 先将询问的权值从小到大排序，由于大的权值包含了小的权值，于是整个过程，居然只需要一次就搞定。 俺是乡下人，第一次见识到这点，吓尿了！╮(╯▽╰)╭
代码：
#define LOCAL
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int maxn=;
/*for point*/
struct node{
int a,b,c;
bool operator <(const node &bn)const {
return c<bn.c;
}
}sac[maxn*];
/*for query*/
struct query{
int id,val;
bool operator <(const query &bn)const {
return val<bn.val;
}
}qq[maxn]; int father[maxn],rank[maxn];
int key[maxn]; void init(int n){
for(int i=;i<=n;i++){
father[i]=i;
rank[i]=;
}
} int fin(int x){
while(x!=father[x])
x=father[x];
return x;
} int unin(int x,int y)
{
x=fin(x);
y=fin(y);
int ans=;
if(x!=y){
ans=rank[x]*rank[y];
if(rank[x]<rank[y]){
rank[y]+=rank[x];
father[x]=y;
}
else{
rank[x]+=rank[y];
father[y]=x;
}
}
return ans;
} int main()
{
#ifdef LOCAL
freopen("test.in","r",stdin);
freopen("test1.out","w",stdout);
#endif
int n,m,q;
while(scanf("%d%d%d",&n,&m,&q)!=EOF)
{
init(n);
for(int i=;i<m;i++){
scanf("%d%d%d",&sac[i].a,&sac[i].b,&sac[i].c);
} for(int i=;i<q;i++){
scanf("%d",&qq[i].val);
qq[i].id=i;
}
sort(sac,sac+m);
sort(qq,qq+q);
int i,j,res=;
for(j=,i=;i<q;i++){
while(j<m&&sac[j].c<=qq[i].val){
res+=unin(sac[j].a,sac[j].b);
++j;
}
key[qq[i].id]=res;
}
for(i=;i<q;i++){
printf("%d\n",key[i]);
}
}
// system("comp"); return ;
}