Description
You are given an undirected graph G with N vertices and M edges. Each edge has a length. Below are two definitions.
Define max_len(p) as the length of the edge with the maximum length of p where p is an arbitrary non-empty path in G.Define min_pair(u, v) as min{max_len(p) | p is a path connecting the vertices u and v.}. If there is no paths connecting u and v, min_pair(u, v) is defined as infinity.Your task is to count the number of (unordered) pairs of vertices u and v satisfying the condition that min_pair(u, v) is not greater than a given integer A.
Input
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 vertices, 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 < 108) describing an edge connecting the vertices a and b with length c. Each of the following Q lines gives a query consisting of a single integer A (0 ≤ A < 108).
Output
Output the answer to each query on a separate line.
Sample Input
4 5 4 1 2 1 2 3 2 2 3 5 3 4 3 4 1 4 0 1 3 2Sample Output
0 1 6 3
题解：
将边和询问都按从小到大排序，然后对于一组询问，我们枚举所有小于当前询问的边，然后把边的两个端点对应的集合进行计算，并查集合并维护
1 #include <algorithm> 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 using namespace std; 8 const int N=100005,M=500005,QM=2000005; 9 typedef long long ll; 10 struct node{ 11 int x,y,dis; 12 bool operator <(const node &pp)const{ 13 return dis<pp.dis; 14 } 15 }e[M]; 16 int gi(){ 17 int str=0;char ch=getchar(); 18 while(ch>'9' || ch<'0')ch=getchar(); 19 while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar(); 20 return str; 21 } 22 int n,m,Q,size[N],fa[N]; 23 int find(int x){ 24 return fa[x]==x?x:fa[x]=find(fa[x]); 25 } 26 struct Question{ 27 int id,x;ll sum; 28 }q[QM]; 29 bool compone(const Question &pp,const Question &qq){ 30 return pp.x<qq.x; 31 } 32 bool comptwo(const Question &pp,const Question &qq){ 33 return pp.id<qq.id; 34 } 35 void work(){ 36 int x,y,dis; 37 n=gi();m=gi();Q=gi(); 38 for(int i=1;i<=m;i++){ 39 e[i].x=gi();e[i].y=gi();e[i].dis=gi(); 40 } 41 for(int i=1;i<=Q;i++)q[i].id=i,q[i].x=gi(); 42 for(int i=1;i<=n;i++)fa[i]=i,size[i]=1; 43 sort(e+1,e+m+1); 44 sort(q+1,q+Q+1,compone); 45 int cnt=0,sum=0,p=1; 46 for(int i=1;i<=Q;i++){ 47 while(e[p].dis<=q[i].x && cnt<n-1 && p<=m){ 48 x=e[p].x;y=e[p].y; 49 if(find(x)==find(y)){ 50 p++;continue; 51 } 52 sum+=(ll)size[find(y)]*size[find(x)]; 53 size[find(x)]+=size[find(y)]; 54 fa[find(y)]=find(x); 55 p++;cnt++; 56 } 57 q[i].sum=sum; 58 } 59 sort(q+1,q+Q+1,comptwo); 60 for(int i=1;i<=Q;i++) 61 printf("%lld\n",q[i].sum); 62 } 63 int main() 64 { 65 work(); 66 return 0; 67 }
转载于:https://www.cnblogs.com/Yuzao/p/7222264.html
