HDU 5441 Travel (离线dsu)

<题目链接>

题目大意：
$n$个点，$m$条边，每条边具有对应的权值，然后进行$k$次询问，每次询问给定一个值，所有权值小于等于这个的边所对应的点能够相连，问每次询问，这些能够相互到达的点所构成的无序点对的个数。

解题分析：
数据比较大，每次询问暴力加边肯定超时，所以考虑离线来搞。进行离线查询，将查询按权值从小到大排序，然后每次询问就不需要全部重新添边，只需要增加多余的那一部分即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+ , M = 5e3+;

#define REP(i,s,t) for(int i=s;i<=t;i++)

struct Edge{

    int u,v,val;

    bool operator < (const Edge&tmp)const{ return val<tmp.val; }

}e[N];

struct Que{ int id,val; }q[M];

bool cmp(Que a,Que b){ return a.val<b.val; }

typedef long long ll;

int n,m,k;

int rk[N],fa[N];

ll ans,res[N];

int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); }

inline void Union(int u,int v){

    int f1=find(u),f2=find(v);

    if(f1!=f2){

        ans+=rk[f1]*rk[f2]*;      //贡献是两个集合点数的乘积

        rk[f1]+=rk[f2];

        fa[f2]=f1;

    }

}

int main(){

    int T;cin>>T;

    while(T--){

        scanf("%d%d%d",&n,&m,&k);

        REP(i,,n)fa[i]=i,rk[i]=;

        REP(i,,m)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].val);

        sort(e+,e++m);

        REP(i,,k)scanf("%d",&q[i].val),q[i].id=i;

        sort(q+,q++k,cmp);

        ans=;

        int loc=;

        REP(i,,k){

            while(loc<=m && e[loc].val<=q[i].val){

                Union(e[loc].u,e[loc].v);

                loc++;

            }

            res[q[i].id]=ans;

        }

        REP(i,,k){

            printf("%lld\n",res[i]);

        }

    }

}