题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4750
题意：给出一个无向图，f(a,b)表示从点a到点b的所有路径中的每条路径的最长边中的最小值，给出 p个询问，每个询问有一个数t，对于每个询问，求有多少对顶点f(a,b)小于t。注意(1,2)和(2,1)是不同的点对
分析：
正过来想不太好做..反过来..看在当前t的限制下..有多少个点对f(u,v)<t...这样答案就是totol-sum...totol是总对数n*(n-1)...sum是当前可联通的..
这样转化后就不难想到将所有的询问从小到大排序..将所有的边从小到大排序..然后根据递增的询问不断地加边统计答案..而要统计答案和维护图的联通关系时用到并查集....如此时间复杂度为O(m).有点像模拟最小生成树的Kurskal
对于每一条边(a,b)，判断两个端点a,b是否属于同一个集合，如果不是，则当前边就是a,b所有路径中要求的“瓶颈边”（因为所有的边是从小到大排序的），这时小于t的点对数为sum加上这两个集合的顶点点个数乘积的两倍，即sum+=num[f1]*num[f2]*2，最后对于每个询问输出total-sum即可。
AC代码如下：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct NODE
{
int u,v,w;
bool operator <(const NODE &a)const{
return w<a.w;
}
}node[];
struct T
{
int d,id;
bool operator <(const T &a)const{
return d<a.d;
}
}t[];
int num[],fa[],ans[];
int find(int x)
{
if(x!=fa[x])
fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
int n,m,j,i,p;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=;i<m;i++)
scanf("%d%d%d",&node[i].u,&node[i].v,&node[i].w);
scanf("%d",&p);
for(i=;i<p;i++)
{
scanf("%d",&t[i].d);
t[i].id=i;
}
sort(node,node+m);
sort(t,t+p);
for(i=;i<n;i++)
{
fa[i]=i;
num[i]=;
}
int total=n*(n-);
int sum=;
j=;
for(i=;i<p;i++)
{
while(j<m&&node[j].w<t[i].d)
{
int f1=find(node[j].u);
int f2=find(node[j].v);
if(f1==f2)
{
j++;
continue;
}
sum+=num[f1]*num[f2]*;
fa[f1]=f2;
num[f2]+=num[f1];
j++;
}
ans[t[i].id]=total-sum;
}
for(i=;i<p;i++)
printf("%d\n",ans[i]);
}
return ;
}