最小差值生成树题解

怎么题解里全是 LCT 而没有整体二分。

来写一发整体二分的题解。

对所有边先按边权排个序，我们记

f_i

为第

i

条边往后找能形成生成树的最小的位置，显然答案就是第

f_i

的边权和第

i

的边权差。

不难发现

f_i

单调不降，遂整体二分。

假设我们现在处理第

l

条边到第

r

条边，答案区间为

s

到

t

，那么取中点

mid = \frac {l + r}{2}

去求

f _ {mid}

，假设我们已经求出，那么就可以对它两边分别去求解。

现在我们考虑怎么求出这个值，其实直接暴力就可以了，从

mid

开始往右找，暴力去判断是否合法，因为是整体二分还要用一个可撤销并查集。

大体思路就是这样的，我的代码里还用了一些优化的小技巧，应该不难理解。

code

CPP

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

vector <int> raw[N];

struct edge {
	int u, v, w;
} e[N];

int n, m, len, ans = 1e9;

int a[N], f[N];

int top, cnt;

int fa[N], sz[N], s[N];

int find (int x) {
	return fa[x] == x ? x : find (fa[x]);
}

inline void merge (int x, int y) {
	x = find (x), y = find (y);
	if (x == y) return;
	if (sz[x] > sz[y]) swap (x, y);
	return fa[x] = y, s[++top] = x, sz[y] += sz[x], cnt++, void ();
}

inline void slipt (int time) {
	while (top > time) {
		int x = s[top--], y = fa[x];
		fa[x] = x, sz[y] -= sz[x], cnt--;
	}
}

#define u e[j].u
#define v e[j].v

void solve (int l, int r, int s, int t) {
	if (l > r or s > t) return;
	
	if (s == t) {
		for (int i = l; i <= r; i++)	
			f[i] = s;
		return;
	}
	
	int mid = (l + r) >> 1, ver = top;
	f[mid] = len + 1;
	
	for (int i = mid; i <= min (r, s - 1); i++)
		for (int j : raw[i]) merge (u, v);
	
	for (int i = max (s, mid); i <= t; i++) {
		for (int j : raw[i]) {
			merge (u, v);
			if (cnt == n - 1) {
				f[mid] = i;
				break;
			}
		}
		
		if (cnt == n - 1) break; 
	}
	
	slipt (ver);
	
	for (int i = mid; i <= min (r, s - 1); i++)
		for (int j : raw[i]) merge (u, v);
	solve (l, mid - 1, s, f[mid] - 1), slipt (ver);
	
	for (int i = max (r + 1, s); i < f[mid]; i++)
		for (int j : raw[i]) merge (u, v);
	solve (mid + 1, r, f[mid], t), slipt (ver);
}

#undef u
#undef v

int main () {
	ios :: sync_with_stdio (false), cin.tie (0), cout.tie (0);
	
	cin >> n >> m;
	for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w, a[i] = e[i].w;
	
	sort (a + 1, a + 1 + m), len = unique (a + 1, a + 1 + m) - a - 1;
	for (int i = 1; i <= m; i++) e[i].w = lower_bound (a + 1, a + 1 + len, e[i].w) - a, raw[e[i].w].emplace_back (i);
	
	for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
	
	solve (1, len, 1, len);
	
	for (int i = 1; i <= len; i++) 
		if (f[i] and f[i] != len + 1) ans = min (ans, a[f[i]] - a[i]);
	cout << ans;
 
	return 0;
}

最小差值生成树题解

文章操作

code

相关推荐

评论

最小差值生成树题解