学步园

               题意:

                        定义f(u,v)为u到v每条路径上的最大边的最小值..现在有一些询问..问f(u,v)>=t的点对有所少对..注意(1,2)和(2,1)是不同的点对...

               题解:

                        正过来想不太好做..反过来..看在当前t的限制下..有多少个点对f(u,v)<t...这样答案就是totol-num...totol是总对数n*(n-1)...num是当前可联通的..

                        这样转化后就不难想到将所有的询问从小到大排序..将所有的边从小到大排序..然后根据递增的询问不断地加边统计答案..而要统计答案和维护图的联通关系时用到并查集....如此时间复杂度为O(m)..

Program:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdlib>
#include<stack>
#include<map>
#define MAXN 10005
#define MAXM 1000505
#define ll long long 
#define eps 1e-10
using namespace std; 
struct node
{
    int x,y,d,next;
}edge[MAXM];
struct NODE1
{
    int x,y,d;
}E[MAXM];
struct NODE2
{
    ll w,id;
}q[MAXM]; 
int father[MAXN];
ll ans[MAXM],num[MAXN];
bool cmp1(NODE1 a,NODE1 b)
{
    return a.d<b.d;
}
bool cmp2(NODE2 a,NODE2 b)
{
    return a.w<b.w;
}
int getfather(int x)
{
    if (father[x]==x) return x;
    return father[x]=getfather(father[x]);
}
int main()
{
    int n,m,x,y,d,p,i,t;
    ll totol,A; 
    while(~scanf("%d%d",&n,&m))
    { 
           for (i=1;i<=m;i++) scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].d); 
           scanf("%d",&p),totol=n*(n-1);
           for (i=1;i<=p;i++) scanf("%I64d",&q[i].w),q[i].id=i;
           sort(E+1,E+1+m,cmp1),sort(q+1,q+1+p,cmp2);
           for (i=0;i<n;i++) father[i]=i,num[i]=1;
           A=0,t=1;
           for (i=1;i<=p;i++) 
           {
                   d=q[i].w;
                   while (t<=m && E[t].d<d)
                   {
                           x=getfather(E[t].x),y=getfather(E[t].y);
                           if (x==y) { t++; continue; }
                           A+=num[x]*num[y]*2;
                           num[y]+=num[x];
                           father[x]=y;                
                           t++;        
                   }
                   ans[q[i].id]=totol-A;
           }
           for (i=1;i<=p;i++) printf("%I64d\n",ans[i]);
    }
    return 0;
}