HDU-5441-离线化并查集-白红宇

HDU-5441-离线化并查集

阅读量：4647 次

发布时间：2019-06-09

本文共 790 字，大约阅读时间需要 2 分钟。

以前没注意过离线化，简而言之就是将所有要处理的目标统一一起处理，从而优化一定的时间或者空间。

这个题目而言就是先将查询储存起来，进行并查集的时候一并处理。

然后来说这个题目，我们可以把每一些满足要求的且可互达的点组成一个并查集，顺便记录每个并查集有几个节点即可。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 using namespace std;int t,n,m,q;int f[20005],s[20005];struct Road{ int u,v,cost; bool operator<(const Road &a)const { return cost
                 
                  query[i].dis) break;//不满足要求就开始处理下一个查询 int u=Find(road[j].u),v=Find(road[j].v); if(u!=v){//合并两个并查集 sum+=s[u]*s[v]*2;//互相可达，那么就是两个并查集点的乘积，根据题意双向算两条 f[v]=u; s[u]+=s[v];//要记得更新根节点有多少个节点 } } query[i].ans=sum; } sort(query,query+q,cmp2); for(int i=0;i