hdu4750Count The Pairs（最小生成树找瓶颈边）

/*
   题意：就是给你一个图，图的每两个点都有多条路径，每一条路径中都有一条最大边，
   所有最大边的最小边（也就是瓶颈边）就是这两点之间的val值！然后给你一个值f，
   问有多少个顶点对的val>=f! (u,v) 和 (v, u)是不同的顶点对！

   思路：最小生成树（kruskral）那么每两个节点(u,v)的瓶颈边就是这一棵树中u到v
         的路径中的最大边值！
         在利用并查集的过程中，A, B两个集合，如果有u属于A，v属于B，且u-v可以将
         A-B集合连接起来，因为边值由小到大选取，那么以u-v边为瓶颈边的节点的个数
         就是[A]*[B]*2;

   注意：图不一定是连通的，开始的时候当成了一棵树，怎么改都不对！
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 10105
#define M 500105
using namespace std;
int f[N];
struct Edge{
    int u, v, w;
    Edge(){}
    Edge(int u, int v, int w){
        this->u=u;
        this->v=v;
        this->w=w;
    }
};

Edge edge[M];
int dist[N];
int rank[N];
int cnt[N];
int edgeN;
int sumN[N];
int n, m;

bool cmp(Edge a, Edge b){
   return a.w < b.w;
}

int getFather(int x){
   return x==f[x] ? x : f[x]=getFather(f[x]);
}

bool Union(int a, int b){
   a=getFather(a);
   b=getFather(b);
   if(a!=b){
      cnt[++edgeN]=sumN[a]*sumN[b]*2;//记录以这一条边为瓶颈边的节点对的个数
      if(rank[a]>rank[b]){
          f[b]=a;
          sumN[a]+=sumN[b];//将b集合放入到a集合中去
      }
      else{
         f[a]=b;
         sumN[b]+=sumN[a];//将a集合放入到b集合中去
         ++rank[b];
      }
      return true;
   }
   return false;
}

void Kruskral(){
   edgeN=0;
   sort(edge, edge+m, cmp);
   for(int i=1; i<=n; ++i)
      f[i]=i, rank[i]=0, sumN[i]=1;
   for(int i=0; i<m; ++i)
    if(Union(edge[i].u, edge[i].v))
       dist[edgeN]=edge[i].w;//记录最小生成树中的边值
   cnt[edgeN+1]=0;
   for(int i=edgeN; i>=1; --i)//统计大于等于第i条边为瓶颈边边值的所有节点对的对数
       cnt[i]+=cnt[i+1];
}

int main(){
    int p;
    while(scanf("%d%d", &n, &m)!=EOF){
        for(int i=0; i<m; ++i){
           int u, v, w;
           scanf("%d%d%d", &u, &v, &w);
           edge[i]=Edge(u+1, v+1, w);
        }
        Kruskral();
        scanf("%d", &p);
        while(p--){
           int x;
           scanf("%d", &x);
           int index=lower_bound(dist+1, dist+edgeN+1, x)-dist;
           if(index>edgeN) printf("0\n");
           else printf("%d\n", cnt[index]);
        }
    }
    return 0;
}

//如果最后只有一棵树的话，这样做就可以了！没想到可能不是仅仅一棵树
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 10105
#define M 500105
using namespace std;
int f[N];
struct Edge{
    int u, v, w;
    Edge(){}
    Edge(int u, int v, int w){
        this->u=u;
        this->v=v;
        this->w=w;
    }
};

Edge edge[M];
int dist[N];
int rank[N];
int cnt[N];
int edgeN;

int n, m;

bool cmp(Edge a, Edge b){
   return a.w < b.w;
}

int getFather(int x){
   return x==f[x] ? x : f[x]=getFather(f[x]);
}

bool Union(int a, int b){
   a=getFather(a);
   b=getFather(b);
   if(a!=b){
      if(rank[a]>rank[b])
          f[b]=a;
      else{
         f[a]=b;
         ++rank[b];
      }
      return true;
   }
   return false;
}

void Kruskral(){
   edgeN=0;
   sort(edge, edge+m, cmp);
   for(int i=1; i<=n; ++i)
      f[i]=i, rank[i]=0;
   for(int i=0; i<m; ++i)
     if(Union(edge[i].u, edge[i].v))
        dist[++edgeN]=edge[i].w;
   cnt[edgeN+1]=0;
   for(int i=edgeN; i>=1; --i){
       cnt[i]=i*2;
       cnt[i]+=cnt[i+1];
   }
}

int main(){
    int p;
    while(scanf("%d%d", &n, &m)!=EOF){
        for(int i=0; i<m; ++i){
           int u, v, w;
           scanf("%d%d%d", &u, &v, &w);
           edge[i]=Edge(u+1, v+1, w);
        }
        Kruskral();
        scanf("%d", &p);
        while(p--){
           int x;
           scanf("%d", &x);
           int index=lower_bound(dist+1, dist+edgeN+1, x)-dist;
           if(index>edgeN) printf("0\n");
           else printf("%d\n", cnt[index]);
        }
    }
    return 0;
}