關于啟發式合并

在我們愉快打暴力的時候，我們會遇到需要合并一些數據的情況。

我們舉一個相當簡單的例子，我們需要很多次合并一些 vector，這個時候作為人類我們會想從小的里邊取放到大的里邊。

若我們需要大到小，就先反過來，再利用對應標記呼喚的方式來進行訪問。

然而對于 stl 來世 swap 就可以。

整個過程是 \(nlogn\) 級別的。

對于任意一個元素，每一次被訪問都會使得它所在的集合至少增長一倍，所以就是 \(nlogn\) 級別的。

[PA 2014] Fiolki

這個東西我們并不知道怎么做，但是發現如果我們在合并的過程之中可以維護每個集合的東西就可以做了。

考慮 vector 維護每個集合中存在的，可能的反應式（這個東西有嚴格的反應順序）。

之后啟發式合并兩個，并查集方便我們檢查反應是否可以進行。

非常完美做完了。

代碼↓

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=1e6+116;
int father[MN], n, m, k, ans=0;
int g[MN], a[MN], b[MN], c[MN], d[MN];
int find(int x){
	if(father[x]!=x) father[x]=find(father[x]);
	return father[x];
}
vector <int> st[MN];
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>m>>k; for(int i=1; i<=n; ++i) cin>>g[i];
	for(int i=1; i<=n; ++i) father[i]=i;
	for(int i=1; i<=m; ++i) cin>>a[i]>>b[i];
	for(int i=1; i<=k; ++i){
		cin>>c[i]>>d[i];
		st[c[i]].push_back(i);
		st[d[i]].push_back(i);
	}
	for(int i=1; i<=m; ++i){
		if(st[a[i]].size()>st[b[i]].size())
			swap(st[a[i]],st[b[i]]);
		father[find(a[i])]=find(b[i]);
		vector <int> tmp;
		for(auto v:st[a[i]]){
			if(find(c[v])==find(d[v])) tmp.push_back(v);
			else st[b[i]].push_back(v);
		}
		sort(tmp.begin(),tmp.end());
		for(auto k:tmp){
			int minn=min(g[c[k]],g[d[k]]);
			ans+=minn*2;
			g[c[k]]-=minn;
			g[d[k]]-=minn;
		}
	}
	cout<<ans<<'\n';
	return 0;
}