题意是要求出给定权值下，满足要求的点对的数目。所谓的要求是，给出两点，之间会有很多路径，这个点对的最小距离是众多路径中，最短的一条路径的长度，路径长度是路径上最长边的长度。于是，认真观察可以发现，两个点能连在一起的前提条件是，之间的的边都小于给定值。于是，用边来构建最小生成树就可以得到这样的一些满足要求的点对了。如果是两个集合因为一条边的加入连在一起了，那么总的点对数目就增加Na*Nb。把答案存下来，然后查询的时候二分找出满足的那一个即可。

代码如下：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int N = 11111;const int M = 55555;struct Edge {    int s, t, c;    Edge() {}    Edge(int s, int t, int c) : s(s), t(t), c(c) {}    bool operator < (Edge x) const { return c < x.c;}} edge[M];struct MFS {    int fa[N], cnt[N];    void init() { for (int i = 0; i < N; i++) fa[i] = i, cnt[i] = 1;}    int find(int x) { return fa[x] = fa[x] == x ? x : find(fa[x]);}    int merge(int x, int y) {        int fx = find(x), fy = find(y);        if (fx == fy) return 0;        int tmp = cnt[fx] * cnt[fy];        fa[fx] = fy;        cnt[fy] += cnt[fx];        return tmp;    }} mfs;typedef pair
           
             PII;const int UPBOUND = 111111111;set
            
              mark;void MST(int n, int m) { sort(edge, edge + m); mfs.init(); mark.clear(); mark.insert(PII(0, 0)); int sum = 0; for (int i = 0; i < m; i++) { if (sum > UPBOUND) break; sum += mfs.merge(edge[i].s, edge[i].t); mark.insert(PII(edge[i].c, sum)); //cout << edge[i].c << ' ' << sum << endl; }}int main() { int n, m, q, x; set
             
              ::iterator si; while (~scanf("%d%d%d", &n, &m, &q)) { for (int i = 0; i < m; i++) { Edge &e = edge[i]; scanf("%d%d%d", &e.s, &e.t, &e.c); } MST(n, m); for (int i = 0; i < q; i++) { scanf("%d", &x); si = mark.upper_bound(PII(x, UPBOUND)); si--; printf("%d\n", (*si).second); } } return 0;}
             
            
           
          
         
        
       
      

 

——written by Lyon