帶權並查集

• 2020 年 7 月 1 日
• 筆記
• 演算法/數據結構 講解

前置芝士

了解普通並查集及普通並查集的數據壓縮。以下為普通的數據壓縮並查集寫法：

const int N = 1e5 + 5;
int n, fa[N];
void find (int x) { //尋找祖先 
	if (fa[x] == x)
		return x;
	return fa[x] = find (fa[x]);
}
void unions (int x, int y) { //合併兩個節點 
	int xx = find (x), yy = find (y);
	if (xx == yy)
		return ;
	fa[xx] = yy;
	return ;
}

普通並查集只能求出節點之間的連接關係，多用於判斷節點之間的連通性，但對於節點之間的其他關係（如距離）則無從下手。
這時候，我們有一個很自然的想法：將普通並查集中的邊附上權值。
如果不考慮路徑壓縮和合併點，則只需要記錄每個點到父節點的路徑長度就可以看。但是如果進行路徑壓縮和合併操作，則需要對點與點之間除連通性以外的關係做特殊處理。

路徑壓縮

給出一個簡單的模型：

若要將點D連接到點A，則點A到點D的距離應保持不變，即 \(val2+val3\) :

得到結論：帶權並查集進行路徑壓縮的時候，當前節點到根節點的距離應為 父節點到根節點的距離+當前節點到父節點的距離。

合併操作

普通並查集進行兩點（以下設兩節點為 \(x,y\) ，合併權值為 \(val1\)）合併的方式，是連接此兩點的兩個祖父節點（以下設兩祖父節點為 \(px,py\) ）。
普通並查集連接邊時不用考慮權值問題，所以可以直接將 \(py\) 點的父節點更改為 \(px\) 節點。但帶權並查集還要求出 \(py\) 到 \(px\) 的權值。
合併問題可以簡化成如下的模型：

假設我們先將 \(x\) 與 \(y\) 連接起來：

則可以得出，\(y\) 到 \(px\) 的距離應為 \(val1 + (x到px的距離)\)。若拆掉 \(y→x\) 的邊，添加 \(py→px\) 的邊，則 \(y\) 到 \(px\) 的距離還應為 \(val1 + (x到px的距離)\)。
顯然：\((py→px) + (y→py) = val1 + (x到px的距離)\)。
即：\((py→px) = val1 + (x到px的距離) – (y→x)\)
由此得到如何求 \(py\) 到 \(px\) 的權值。

板子程式碼

const int N = 1e5 + 5;
int n, fa[N], val[N]; //val[x]=x節點到父節點的距離 
void find (int x) { //尋找祖先 
	if (fa[x] == x)
		return x;
	int t = fa[x];
	fa[x] = find (fa[x]);
	val[x] += val[t];
	return ;
}
void unions (int x, int y, int v) { //合併兩個節點 
	int xx = find (x), yy = find (y);
	if (xx == yy)
		return ;
	fa[xx] = yy;
	val[xx] = -val[x] + val[y] + v;
	return ;
}

例題

HDU3038 How Many Answers Are Wrong

題目大意

有 \(n\) 個整數（包括負數和0），不知道每個數的具體值，但是會給定 \(m\) 次某兩個下標範圍內的數值的和。求 \(m\) 次中，與前面給出的條件自相矛盾的次數。

解法

設每次給定的區間範圍為 \(l,r\) ，區間和為 \(val\) ；
首先可以得到一個命題：能夠確認為自相矛盾的情況，只有 「明確出現了從前面給定的已知合理條件中，可以得出 \(l\) 到 \(r\) 的區間和，並且該區間和與 \(val\) 不相等。」
若考慮進行前綴和預處理，則會發現本題中判斷自相矛盾的方式與帶權並查集的端點合併操作有著異曲同工之妙。但是若直接將該區間的左端點和右端點連接起來並附上權值，會出現 「區間和包括端點和」 的問題。
解決辦法是將 \(l-1\) 和 \(r\) 連接起來並附上區間和，而不是 \(l\) 和 \(r\)。
（看心情補詳細圖解）

程式碼

（注意HDU和POJ不支援使用 #include <bits/stdc++.h> ）

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, ans, fa[N], val[N];
int find (int x) {
	if (fa[x] == x)
		return x;
	int t = fa[x];
	fa[x] = find (fa[x]);
	val[x] += val[t];
	return fa[x];
}
void unions (int x, int y, int v) {
	int xx = find (x), yy = find (y);
	fa[xx] = yy;
	val[xx] = -val[x] + val[y] + v;
	return ;
}
int main () {
	while (scanf ("%d%d", &n, &m) != EOF) {
		for (int i = 0; i <= n; i ++) {
			fa[i] = i;
			val[i] = 0;
		}
		ans = 0;
		for (int i = 1; i <= m; i ++) {
			int l, r, sum;
			scanf ("%d%d%d", &l, &r, &sum);
			l --;
			int x = find (l), y = find (r);
			if (x == y) {
				if (val[l] - val[r] != sum)
					ans ++;
			} else
				unions (l, r, sum);
		}
		printf ("%d\n", ans);
	}	
	return 0;
}