【HDU 3938】Portal （并查集+离线）

http://acm.hdu.edu.cn/showproblem.php?pid=3938

两点之间建立传送门需要的能量为他们之间所有路径里最小的T，一条路径的T为该路径上最长的边的长度。现在 Q 个询问，问 L 能量可以选择多少种不同点对？

 

因为小的能量找出的点对，在大的能量下肯定也能建立传送门，因此把询问记下来，按询问的能量从小到大计算，这样离线处理。

从小到大枚举添加每条能量不超过当前能量且还没枚举过的边，

如果它连接的两个点属于不同联通块，就加上这条边。

能选择的点对就有两个联通块的点数之积那么多种。

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
#define N 10005
struct edge{
    int u,v,w;
}e[N*5];
int cmp0(edge a, edge b){
    return a.w<b.w;
}
struct question{
    int id,v,ans;
}q[N];
int cmp(question a,question b){
    return a.v<b.v;
}
int cmp2(question a, question b){
    return a.id<b.id;
}
int n,m,Q;
int fa[N],num[N];
int find(int v){
    int k,j,fv=v;
    while(fv!=fa[fv])
        fv=fa[fv];
    k=v;
    while(k!=fv){
        j=fa[k];
        fa[k]=fv;
        k=j;
    }
    return fv;
}
void init(){
    for(int i=1;i<=n;i++)
        fa[i]=i,num[i]=1;
}
int main() {
    while(~scanf("%d%d%d",&n,&m,&Q)){
        init();

        for(int i=1;i<=m;i++)
            scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
        sort(e+1,e+1+m,cmp0);
        for(int i=1;i<=Q;i++){
            scanf("%d",&q[i].v);
            q[i].id=i;
            q[i].ans=0;
        }
        sort(q+1,q+1+Q,cmp);
        int l=1;
        for(int i=1;i<=Q;i++){
            q[i].ans=q[i-1].ans;
            for(;l<=m&&e[l].w<=q[i].v;l++){
                int fu=find(e[l].u),fv=find(e[l].v);
                if(fu!=fv){
                    fa[fv]=fu;
                    q[i].ans+=num[fu]*num[fv];
                    num[fu]+=num[fv];
                }
            }
        }
        sort(q+1,q+1+Q,cmp2);
        for(int i=1;i<=Q;i++)
            printf("%d\n",q[i].ans);
    }
    return 0;
}