[PHP知识库]带权并查集

带权并查集

大神的博客链接在这里！

权值：记录 当前结点与根结点之间的权值，用来处理结点之间的相对关系

需要注意 路径压缩 、 并查集合并 、以及 判断是否符合条件 的时候

路径压缩：

int fin(int x){
    if(fa[x] != x) {
        int t = fa[x];
        fa[x] = fin(t);
        va[x] += va[t];
	}
    return fa[x];
}

• 父节点权值先更新，子节点再更新
• 路径压缩之后，再访问的父节点就是根节点，权值也不会再发生变化（va[根结点] = 0）

并查集合并：

int x,y,s;
cin>>x>>y>>s;

int fx = fin(x), fy = fin(y);
fa[fx] = fy; // 根节点取x还是取y，需要根据题目确定
va[fx] = -va[x] + va[y] + s;

• 合并之后的根节点更新为fy
• x集的根节点的权值更新：fx不再是合并之后的并查集的根节点，因此需要更新权值，记录fx到fy的权值。
• x集合的父节点仍然是fx，因此更新 va[fx] 时，以x为尾结点，连接y集合。 fx的权值变化：从 fx 返回 x 再到 y 最后到 fy（路径就是x ? fx ? y ? fy 或者x ? y ? fx ? fy ）
• x结点的权值在它下一次使用fin()函数时更新

判断是否符合条件：

int x, y, s;
cin>> x>> y>> s;

int fx = fin(x), fy = fin(y);
if(fx == fy && s != va[x] - va[y])// 注：va[x]>va[y]
    flag ++;

• 不再一个集合内无法判断是否符合已知条件
• 合并到一个集合之后，才能判断根据后续条件判断结点
• 顺序：新结点出现 - 合并到集合 - 基于该结点新条件出现- 判断该条件

例题部分

带权并查集 - 例题：How Many Answers Are Wrong

• 链接：http://acm.hdu.edu.cn/showproblem.php?pid=3038

• 题意：判断某一区间和是否符合已知条件

• 坑点：多组输入、数字从0开始

  #include <bits/stdc++.h>
  using namespace std;
  
  const int N = 2e5+10;
  int fa[N],va[N];
  
  int fin(int x){
      if(fa[x] != x) {
          int t = fa[x];
          fa[x] = fin(t);
          va[x] += va[t];
      }
      return fa[x];
  }
  
  int main(){
  
      int n, m;
  
      while(~scanf("%d%d",&n,&m)){
  
          int flag = 0;
          for(int i = 0; i <= n; i++) fa[i] = i,va[i] =  0;
  
          for(int i = 0 ; i< m; i++){
              int x,y,s;
              scanf("%d%d%d",&x,&y,&s);
              x--;
  
              int fx = fin(x), fy = fin(y);
  
              if(fx != fy) {
                  fa[fx]  = fy;
                  va[fx] = -va[x] + va[y] + s;
              }
              if(fx == fy && s != va[x] - va[y]) flag ++;
              
          }
  
          cout<<flag<<endl;
  
      }
      return 0;
  }

种类并查集 - 例题1：食物链

• 题目链接:https://vjudge.z180.cn/problem/POJ-1182

• 分组：A?B?C 表示 A吃B，B吃C，C吃A。也就是分成三组：0表示同类，1表示吃，2表示被吃

#include<iostream>
#include<stdio.h>
using namespace std;

const int N = 5e4+10;
int fa[N],va[N]={0};

int fin(int x){
    if(x != fa[x]){
        int t = fa[x];
        fa[x] = fin(t);
        va[x] = (va[x] + va[t])%3;
    }
    return fa[x];
}

int main(int argc, const char** argv) {
    
    int n, m, ans=0;
    scanf("%d%d",&n,&m);

    for(int i = 1; i <= n; i++) fa[i] = i;

    while(m--)
    {
        int s,x,y;
        scanf("%d%d%d",&s,&x,&y);

        if(x>n || y>n || (x==y && s==2)) ans++;

        else {
            int fx = fin(x), fy = fin(y);
            if(fx != fy) {
                fa[fx] = fy;
                va[fx] = (-va[x] + va[y] + s-1 )%3;
            }
            else if(s-1 != (va[x] - va[y] +3 )%3) ans ++;
        }        
    }
    cout<<ans<<endl;
    
    return 0;
}

种类并查集 - 例题2：P1525 [NOIP2010 提高组] 关押罪犯

• 题目链接：https://www.luogu.com.cn/problem/P1525

• 题意：根据怨气值将罪犯分配到两个监狱中，将怨气值最小化，输出监狱中最大的怨气值

• 思路：先处理怨气值最大的组，将它分配到两个监狱中，如果已经在同一个监狱中，就说明当前组是需要输出的最大怨气值

• 分类：需要分成两组：0表示在同一个监狱中，1表示不再同一个监狱中

#include <bits/stdc++.h>
using namespace std;

const int N = 2e4+10,M = 1e5+10;

struct node {
    int x,y,s;
    bool operator < (const node &b) const {
        return s > b.s;
    }
}st[M];

int fa[N],va[N]={0};

int fin(int x){
    if(fa[x] != x) {
        int t = fa[x];
        fa[x] = fin(t);
        va[x] = (va[x] + va[t])%2;
    }
    return fa[x];
}

int main(){

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

    for(int i = 1; i<= n; i++)  fa[i] = i;
    
    for(int i = 0; i < m; i++)
        scanf("%d%d%d",&st[i].x,&st[i].y,&st[i].s);

    sort(st,st+m);

    for(int i = 0 ; i < m; i++){
        int x = st[i].x , y= st[i].y, s = st[i].s;
        
        int fx = fin(x), fy = fin(y);
        
        if(fx == fy&& (va[x] - va[y]) %2==0){
            cout<<s<<endl;
            return 0;            
        }
        else {
            fa[fx] =  fy;
            va[fx] = (-va[x] + va[y] +1)%2;
        }
    }

    cout<<0<<endl;

    return 0;
}