P1525 [NOIP2010 提高组] 关押罪犯 题解 | 种类并查集

P1525 [NOIP2010 提高组] 关押罪犯 题解 | 种类并查集 前言

并查集，想必大家并不陌生，她可以方便快捷地合并、查询两个集合。

例题：P1551 亲戚。

不过我们今天的重点不是普通并查集太简单了（雾，而是并查集的一种变体，种类并查集。

Part1. 种类并查集

种类并查集一般是把元素分成确定的集合数。

例如 P1525 [NOIP2010 提高组] 关押罪犯，把若干个罪犯分成 2 2 2 个集合，而且给关系很特别，给的是 2 2 2 个数不在一个集合。此时，种类并查集就派上用场了。

Part2. 实现

先看代码：

#include 
using namespace std;

int n,m;
struct edge{
    int u,v,w;
    bool operator<(const edge&_)const{return w>_.w;}
}e[100005];
int fa[20005<<1];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int a,int b){
    int x=find(a),y=find(b);
    if(x!=y){
        fa[x]=y;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=2*n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    sort(e+1,e+m+1);
    for(int i=1;i<=m;i++){
        int x=e[i].u,y=e[i].v;
        if(find(x)==find(y)){
            cout< 
看到这里，想必大家有很多疑惑吧，这里一一解答。
 
Q1. 为什么开 
    
     
      
       
        2
       
       
        ×
       
       
        n
       
      
      
       2 times n
      
     
    2×n 的大小？ 
因为有两个集合，所以我们复制一个影子，就是 
    
     
      
       
        2
       
       
        ×
       
       
        n
       
      
      
       2times n
      
     
    2×n，例如 
    
     
      
       
        x
       
       
        ,
       
       
        y
       
      
      
       x,y
      
     
    x,y 不在同一个集合，那我们就把 
    
     
      
       
        x
       
      
      
       x
      
     
    x 和 
    
     
      
       
        y
       
       
        +
       
       
        n
       
      
      
       y+n
      
     
    y+n 合并，
    
     
      
       
        x
       
       
        +
       
       
        n
       
      
      
       x+n
      
     
    x+n 和 
    
     
      
       
        y
       
      
      
       y
      
     
    y 合并。查找时，依然是 
    
     
      
       
        f
       
       
        
         a
        
        
         x
        
       
       
        =
       
       
        f
       
       
        
         a
        
        
         y
        
       
      
      
       fa_x=fa_y
      
     
    fax​=fay​ 就在同一集合，反之亦然。
 
Q2. 为什么排序？ 
Z 市长要看到最大的影响值，所以。
 
Part3. 总结 
并查集的变种很多，应用很广泛，很强大，需要好好掌握。
 
可以点个赞再走吗 QAQ
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714444.html