[带权并查集] Zjnu Stadium HDU - 3047 &关押罪犯[+二分图解法] P1525(洛谷) & [NOI2001]食物链

带权并查集分析A，B之间的相对距离，可以得到rnk[fa] = rnk[A]+x-rnk[B]。注意到这时，对于原来的A的树，只更新了fa跟结点的权值，那么其它结点的更新在查找的那一步里面实行了。
维护是相对距离

一开始 ab之间关系 a到b是s 在 fa fb 不一样是我们可以当 a到fa b到fb 还有 a到b距离s 是向量那么 rnk[fb]=rnk[a]-rnk[b]+s

种类并查集很多耶可以转到带权上orz

http://acm.hdu.edu.cn/showproblem.php?pid=3047
Zjnu Stadium HDU - 3047 带权并查集板子题

板子

#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=200000+10;
////const int INF = 0x3f3f3f3f;
const int gxs = 3;
int n,m;
int pre[maxn],rnk[maxn];

void init() {
	for(int i=0; i<maxn; i++) pre[i]=i,rnk[i]=0;
}
//查找
int finds(int x){
	if(x==pre[x]) return x;
	int t=pre[x];
	pre[x]=finds(pre[x]);
	rnk[x]+=rnk[t];
	return pre[x];
}

//新建关系
void unions(int x,int y,int s) {
	int fx=finds(x),fy=finds(y);
	if (fx!=fy) {
		pre[fy]=fx;
		rnk[fy]=rnk[x]-rnk[y]+s;//+mod;
	// rnk[fy]%=mod;
	}
}

int main() {
	int b,a,k;
	ios::sync_with_stdio(false);
	while(cin>>n>>m){
		init();
		int ans=0;
		for(int i=0;i<m;i++){
			cin>>a>>b>>k;
			if(finds(a)==finds(b)){
				if(rnk[a]+k!=rnk[b]) ans++;
			}else{
				unions(a,b,k);
			}
		}
		cout<<ans<<endl;
	} 
	return 0;
}

之后2题只是在带权并查集上加了mod
就比如食物链 a吃b b吃c c吃a 一样 0 表示同类 1 表示x吃y 2表示y吃x
他们关系成环所以知道 a b距离1 b c 距离又是 1 很显然 a c距离是2 这样就是 c吃a 每次分析相对位置就好

#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=200000+10;
////const int INF = 0x3f3f3f3f;
//const long long mod = 1e9+7;
const int gxs = 3;
int n,m;
const int mod=3;

int pre[maxn],rnk[maxn];
//查找 

void init(){
    for(int i=0;i<maxn;i++) pre[i]=i,rnk[i]=0;
}
int finds(int x) 
{
    if(x==pre[x]) return x;
    else 
    {
        int root=finds(pre[x]);     // 找到根节点
        rnk[x]+=rnk[pre[x]];       // 权值合并，更新
        rnk[x]%=mod;
        return pre[x]=root;        // 压缩路径
    }
}

//新建关系
void unions(int x,int y,int m){
    int a=finds(x),b=finds(y);
    if(a!=b){
        pre[b]=a;
        rnk[b]=rnk[x]+m-rnk[y];
        rnk[b]+=gxs;
        rnk[b]%=gxs;
    }
} 

int main() {
    int b,a,k;
    ios::sync_with_stdio(false);
    cin>>n>>m;
        init();
        int ans=0;
        for(int i=0;i<m;i++){
            cin>>k>>a>>b;
            if((k==2&&a==b)||a>n||b>n||a<=0||b<=0) {
                ans++;
            }
            else if(k==1){
                if(finds(a)==finds(b)&&(rnk[a]!=rnk[b])) ans++;
                else  unions(a,b,0);
            }
            else if(k==2){
                if(finds(a)==finds(b)&&(rnk[a])!=(rnk[b]+2)%mod) ans++;
                else  unions(a,b,1);
            }
        }
        cout<<ans<<endl;
    
    return 0;
}

排序是必须的，我们要尽可能让危害大的罪犯在两个监狱里。
那么，再结合敌人的敌人和自己在一个监狱的规律合并。
当查找时发现其中两个罪犯不可避免地碰撞到一起时，只能将其输出并结束。
带权 mod取2；
wa 第一个点就是没有冲突时输出 0 orz

[带权并查集] Zjnu Stadium HDU - 3047 &关押罪犯[+二分图解法] P1525(洛谷) & [NOI2001]食物链

全站热榜