带权值并查集（转）

快来打我* 2021-11-18 00:28 282阅读 0赞

**\[POJ 1988\] Cube Stacking**  
　　我们需要新增两种属性cnt\[i\]cnt\[i\]与s\[i\]s\[i\]，分别表示ii之下的块数和ii所在堆的数量。在路径压缩时，cnt\[i\] += cnt\[f\[i\]\] ，另外在连接操作时，需要动态更新cnt\[find(u)\]和s\[find(v)\]的信息。

1 #include <iostream>
     2 #define lson l,m,rt<<1
     3 #define rson m+1,r,rt<<1|1
     4 #define clo std::ios::sync_with_stdio(false)
     5 using namespace std;
     6 const int maxn=1e5+5;
     7 const int N=300004;
     8 int f[N],cnt[N],s[N];
     9 void init(){
    10     for(int i=1;i<=N;i++){
    11         //初始化每个的根都是自己，然后所在堆只有一个 
    12         f[i]=i;
    13         s[i]=1;
    14     }
    15 }
    16 
    17 int find(int x){
    18     int rt;
    19     //在路径压缩的时候更新cnt的值，根就是每堆最下面的那个 
    20     if(f[x]!=x){
    21         int fa=f[x];
    22         f[x]=find(f[x]);
    23         cnt[x]+=cnt[fa];
    24     }
    25     //都没用路径压缩
    26     return f[x]; 
    27 }
    28 int main(){
    29     std::ios::sync_with_stdio(false);
    30     int p;cin>>p;
    31     init();
    32     while(p--){
    33         //cout <<"p=="<<p<<endl;
    34         char c;
    35         cin>>c;
    36         if(c=='M')
    37         {
    38             int a,b;cin>>a>>b;
    39             int fa=find(a);int fb=find(b);
    40             if(fa!=fb){
    41                 f[fa]=fb;
    42                 cnt[fa]=s[fb];
    43                 s[fb]+=s[fa];
    44             }
    45         }
    46         else
    47         {
    48             int u;
    49             cin>>u;
    50              find(u);
    51             cout <<cnt[u]<<endl;    
    52         }
    53     }
    54     return 0;
    55 }

**\[HDU 3635\] Dragon Balls**  
　　我们需要新增两种属性cnt\[i\]cnt\[i\]和trans\[i\]trans\[i\]，分别表示该堆数量和转移次数。在路径压缩时，trans\[x\] += trans\[fa\]。在合并时，动态更新被合并树的堆数量，并增加合并树的转移次数cnt\[fy\] += cnt\[fx\]，trans\[fx++\]。

1 #include <iostream>
     2 #define lson l,m,rt<<1
     3 #define rson m+1,r,rt<<1|1
     4 #define clo std::ios::sync_with_stdio(false)
     5 using namespace std;
     6 const int maxn=1e5+5;
     7 int f[maxn],s[maxn],c[maxn];
     8 void init(int n){
     9     for(int i=1;i<=n+1;i++){
    10         //根，以这个为根有几个，被合并次数 
    11         f[i]=i;s[i]=1;c[i]=0;
    12     }
    13 }
    14 //根是没有被转移过的，那么合并之后让根=1；之后路径压缩的时候所有的后继都会更新根的转移次数
    15 //那么转移次数就被更新了，wawawawawawawawa,这怎么操作出来的 
    16 int find(int x){
    17     if(x!=f[x]){
    18         int fa=f[x];
    19         f[x]=find(f[x]);
    20         c[x]+=c[fa];
    21     }
    22     return f[x];
    23 }
    24 int main(){
    25     std::ios::sync_with_stdio(false);
    26     int t;cin>>t;
    27     int cnt=1;
    28     while(t--){
    29         cout <<"Case "<<cnt++<<":"<<endl;
    30         int n,m;cin>>n>>m;
    31         init(n);
    32         for(int i=1;i<=m;i++){
    33             char cha;cin>>cha;
    34             if(cha=='T'){
    35                 int a,b;cin>>a>>b;
    36                 int fa=find(a);int fb=find(b);
    37                 if(fa!=fb){
    38                     f[fa]=fb;
    39                     s[fb]+=s[fa];
    40                     c[fa]++;        
    41                 }
    42             }
    43             else
    44             {
    45                 int a;cin>>a; 
    46                 int fa=find(a);
    47                 cout <<fa<<" "<<s[fa]<<" "<<c[a]<<endl;
    48             }
    49         }
    50     }
    51     return 0;
    52 }

** A - How Many Answers Are Wrong HDU - 3038**

这个题写了好久，一开始怎么也想不通怎么就与并查集有关。后来想明白了就很容易理解了。

通过前缀和把每个查询区间用并查集连接起来，以一个基准位置为根，把在这查询之前没有出现过的位置都加入到并查集中，如果出来了，那看与已经出现的情况值是否冲突，如果冲突那么就错误ans+1。详细的实现看代码中的解释。

1 #include <iostream>
     2 #define lson l,m,rt<<1
     3 #define rson m+1,r,rt<<1|1
     4 #define clo std::ios::sync_with_stdio(false)
     5 using namespace std;
     6 const int MAXN=2e5+5;
     7 typedef long long ll;
     8 ll f[MAXN],cnt[MAXN];
     9 void init(int n)
    10 {
    11     for(int i=0;i<=n;i++){
    12         f[i]=i,cnt[i]=0;
    13     }
    14 }
    15 
    16 int find(int x){
    17     if(x!=f[x]){
    18         int fx=f[x];
    19         f[x]=find(f[x]);
    20         cnt[x]+=cnt[fx];
    21     }
    22     //通过路径压缩的过程把cnt更新到直接以根节点为前驱的和，即（cnt[x]=sum[x]-sum[f[x]])
    23     //因为路径压缩，这里的f[x]就是根了，这里的路径压缩写法非常简洁， 
    24     return f[x];
    25 }
    26 
    27 int main(){
    28     std::ios::sync_with_stdio(false);
    29     int n,m;
    30     init(n);
    31     while(cin>>n>>m){
    32         int ans=0;
    33         while(m--)
    34         {
    35             
    36             int a,b,w;cin>>a>>b>>w;
    37             a=a-1;
    38             int fa=find(a);int fb=find(b);
    39             if(fa==fb)
    40             {
    41                 if(cnt[b]-cnt[a]!=w)
    42                     ans++;
    43                 //如果都已经在一个集合中了，那很显然如果集合中保留的信息与查询信息不同，则ans++ 
    44                 //这里的cnt都是以根为基准点的，所以真的很显然 
    45                 
    46             }
    47             else
    48             {
    49                 f[fb]=fa;
    50                 cnt[fb]=cnt[a]+w-cnt[b];
    51                 //这个式子有点难理解，但是你画个图就很容易看出来了
    52                 //更新后 有个等式 
    53                 //因为cnt[b]+cnt[fb]==cnt[a]+w;移项就能的cnt[fb] 
    54             }
    55         }
    56         cout <<ans<<endl;
    57     }
    58     
    59     return 0;
    60 }

# #

转载于:https://www.cnblogs.com/Msmw/p/11249955.html