学步园

题意：求出有多少个两点之间所有路径的最大边的最小值不小于t。

思路：刚开始的思路是将边排序，把所有的t也排序，然后对于每个t，将小于t的边取出来，看有多少种联通的组合，用总的组合数减去就得到了，因为写错了一个地方tle了，就怀疑算法有问题。现在想想这就是求最小生成树的过程，小boss说了，最小生成树求出来了答案就全出来了。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
const int N=11000;
const int inf=0x3fffffff;
using namespace std;
int f[N],head[N],num,n,m,vis[N],de[N];
struct edge
{
    int x,y,w;
}e[N*50],q[N*10];
int cmp(void const *a,void const *b)  
{  
    edge *c,*d;  
    c=(edge *)a;  
    d=(edge *)b;  
    return c->w-d->w;  
}
int amp(void const *a,void const *b)  
{  
    edge *c,*d;  
    c=(edge *)a;  
    d=(edge *)b;  
    return c->x-d->x;  
}
int find(int a)
{
    if(a!=f[a])
        f[a]=find(f[a]);
    return f[a];
}
int main()
{
    int i,k,x,y,j,sum;
    while(scanf("%d%d",&n,&m)!=-1)
    {
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
            e[i].x++;e[i].y++;
        }
        qsort(e,m,sizeof(e[0]),cmp);
        scanf("%d",&k);
        for(i=0;i<k;i++)
        {
            scanf("%d",&q[i].x);
            q[i].w=i;
        }
        qsort(q,k,sizeof(q[0]),amp);
        for(i=1;i<=n;i++)
        {f[i]=i;de[i]=1;}
        sum=n*n-n;
        for(j=0,i=0;j<k;j++)
        {
            while(sum>0&&e[i].w<q[j].x&&i<m)//sum==0时就是求出了最小生成树了
            {
                x=find(e[i].x);
                y=find(e[i].y);
                i++;//刚开始写到下面，tle了
                if(x==y)continue;
                sum-=(2*(de[x]*de[y]));
                f[x]=find(y);
                de[y]+=de[x];
            }
                q[j].y=sum;
        }
        qsort(q,k,sizeof(q[0]),cmp);
        for(i=0;i<k;i++)
            printf("%d\n",q[i].y);
    }
    return 0;
}