帶權并查集
帶權并查集
【概述】 1、定義:帶權并查集即是結點存有權值信息的并查集。
2、適用:當兩個元素之間的關系可以量化,并且關系可以合并時,可以使用帶權并查集來維護元素之間的關系。
3、權值:帶權并查集每個元素的權通常描述其與并查集中祖先的關系,這種關系如何合并,路徑壓縮時就如何壓縮。
4、與并查集的區別:帶權并查集可以推算集合內點的關系,而一般并查集只能判斷屬于某個集合。
【具體實現】


例:https://hihocoder.com/problemset/problem/1515
#include <iostream> #include <cstdio> using namespace std; const int maxn=100005; int n,m,q; int f[maxn],v[maxn];//i的父親,i與v[i]之間的關系; void init() { for(int i=1;i<=n;i++){ f[i]=i,v[i]=0; } } int fin(int x) { if(x!=f[x]){ int fa=f[x]; f[x]=fin(f[x]); v[x]+=v[fa]; } return f[x]; } int unit(int x,int y,int s) { int fa=fin(x); int fb=fin(y); if(fa!=fb){ f[fa]=fb; v[fa]=s-v[x]+v[y]; } } bool same(int x,int y) { return fin(x)==fin(y); } int main() { scanf("%d%d%d",&n,&m,&q); int a,b,c; init(); for(int i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); unit(a,b,c); } for(int i=0;i<q;i++) { scanf("%d%d",&a,&b); if(!same(a,b)){ printf("-1\n"); }else{ printf("%d\n",v[a]-v[b]); } } return 0; }

浙公網安備 33010602011771號