1 /* 2    题意：就是给你一个图，图的每两个点都有多条路径，每一条路径中都有一条最大边， 3    所有最大边的最小边（也就是瓶颈边）就是这两点之间的val值！然后给你一个值f， 4    问有多少个顶点对的val>=f! (u,v) 和 (v, u)是不同的顶点对！ 5  6    思路：最小生成树（kruskral）那么每两个节点(u,v)的瓶颈边就是这一棵树中u到v 7          的路径中的最大边值！ 8          在利用并查集的过程中，A, B两个集合，如果有u属于A，v属于B，且u-v可以将 9          A-B集合连接起来，因为边值由小到大选取，那么以u-v边为瓶颈边的节点的个数10          就是[A]*[B]*2;11 12    注意：图不一定是连通的，开始的时候当成了一棵树，怎么改都不对！13 */14 #include<iostream>15 #include<cstring>16 #include<cstdio>17 #include<algorithm>18 #define N 1010519 #define M 50010520 using namespace std;21 int f[N];22 struct Edge{23     int u, v, w;24     Edge(){}25     Edge(int u, int v, int w){26         this->u=u;27         this->v=v;28         this->w=w;29     }30 };31 32 Edge edge[M];33 int dist[N];34 int rank[N];35 int cnt[N];36 int edgeN;37 int sumN[N];38 int n, m;39 40 bool cmp(Edge a, Edge b){41    return a.w < b.w;42 }43 44 int getFather(int x){45    return x==f[x] ? x : f[x]=getFather(f[x]);46 }47 48 bool Union(int a, int b){49    a=getFather(a); 50    b=getFather(b);51    if(a!=b){52       cnt[++edgeN]=sumN[a]*sumN[b]*2;//记录以这一条边为瓶颈边的节点对的个数53       if(rank[a]>rank[b]){54           f[b]=a;55           sumN[a]+=sumN[b];//将b集合放入到a集合中去56       }57       else{58          f[a]=b;59          sumN[b]+=sumN[a];//将a集合放入到b集合中去60          ++rank[b];61       }62       return true;63    }64    return false;65 }66 67 void Kruskral(){68    edgeN=0;69    sort(edge, edge+m, cmp);70    for(int i=1; i<=n; ++i)71       f[i]=i, rank[i]=0, sumN[i]=1;72    for(int i=0; i<m; ++i)73     if(Union(edge[i].u, edge[i].v))74        dist[edgeN]=edge[i].w;//记录最小生成树中的边值75    cnt[edgeN+1]=0;76    for(int i=edgeN; i>=1; --i)//统计大于等于第i条边为瓶颈边边值的所有节点对的对数77        cnt[i]+=cnt[i+1];78 }79 80 int main(){81     int p;82     while(scanf("%d%d", &n, &m)!=EOF){83         for(int i=0; i<m; ++i){84            int u, v, w;85            scanf("%d%d%d", &u, &v, &w);86            edge[i]=Edge(u+1, v+1, w);87         }88         Kruskral();89         scanf("%d", &p);90         while(p--){91            int x;92            scanf("%d", &x);93            int index=lower_bound(dist+1, dist+edgeN+1, x)-dist;94            if(index>edgeN) printf("0\n");95            else printf("%d\n", cnt[index]);96         }97     }98     return 0;99 }

//如果最后只有一棵树的话，这样做就可以了！没想到可能不是仅仅一棵树
 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #define N 10105 6 #define M 500105 7 using namespace std; 8 int f[N]; 9 struct Edge{10     int u, v, w;11     Edge(){}12     Edge(int u, int v, int w){13         this->u=u;14         this->v=v;15         this->w=w;16     }17 };18 19 Edge edge[M];20 int dist[N];21 int rank[N];22 int cnt[N];23 int edgeN;24 25 int n, m;26 27 bool cmp(Edge a, Edge b){28    return a.w < b.w;29 }30 31 int getFather(int x){32    return x==f[x] ? x : f[x]=getFather(f[x]);33 }34 35 bool Union(int a, int b){36    a=getFather(a); 37    b=getFather(b);38    if(a!=b){39       if(rank[a]>rank[b])40           f[b]=a;41       else{42          f[a]=b;43          ++rank[b];44       }45       return true;46    }47    return false;48 }49 50 void Kruskral(){51    edgeN=0;52    sort(edge, edge+m, cmp);53    for(int i=1; i<=n; ++i)54       f[i]=i, rank[i]=0;55    for(int i=0; i<m; ++i)56      if(Union(edge[i].u, edge[i].v))57         dist[++edgeN]=edge[i].w;58    cnt[edgeN+1]=0;59    for(int i=edgeN; i>=1; --i){60        cnt[i]=i*2;61        cnt[i]+=cnt[i+1]; 62    }63 }64 65 int main(){66     int p;67     while(scanf("%d%d", &n, &m)!=EOF){68         for(int i=0; i<m; ++i){69            int u, v, w;70            scanf("%d%d%d", &u, &v, &w);71            edge[i]=Edge(u+1, v+1, w);72         }73         Kruskral();74         scanf("%d", &p);75         while(p--){76            int x;77            scanf("%d", &x);78            int index=lower_bound(dist+1, dist+edgeN+1, x)-dist;79            if(index>edgeN) printf("0\n");80            else printf("%d\n", cnt[index]);81         }82     }83     return 0;84 }