自动搬运

查看原文

来自洛谷，原作者为

	djh123 qwq

搬运于2025-08-24 22:12:45，当前版本为作者最后更新于2019-11-09 07:45:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

因为$\text{mex}$是不在生成树内的最小的自然数，那我们可以考虑枚举答案是$x$，$\text{check}$的时候，如果一条边的边权是$x$，那么这条边就不应该出现在生成树里，否则一定非法。

那么就有一个比较显然的做法：枚举答案$x$，把边权为$x$的所有边删掉，看剩下的边能不能求出一棵生成树。

这样直接暴力去做的复杂度是$O(mw\log m)$的，对于这种删掉一部分边的问题，我们可以考虑用分治去优化这个过程，那么我们就用$solve(l,r)$就表示权值范围在$[l,r]$的边没有加进去，每次添加$[l,mid]$到$[mid+1, r]$，添加$[mid+1, r]$到$[l, mid]$，用可撤销并查集维护连通性即可，复杂度$O(m\log m \log w)$，实现的稍微好一点就能通过了。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e6 + 50, M = 4e6 + 50;
int head[N], to[M], nxt[M], val[M], tot;
bool vis[N];

int fa[N], siz[N], cnt, n, m, ans = 0x3f3f3f3f;
struct node {
	int u, v, w;
}e[M];
bool operator < (const node &a, const node &b) {
	return a.w < b.w;
}

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

int unit(int x, int y) {
	int fx = find(x), fy = find(y);
	if(fx == fy) return 0;
	if(siz[fx] > siz[fy]) { fa[fy] = fx; siz[fx] += siz[fy]; return fy; }
	else { fa[fx] = fy; siz[fy] += siz[fx]; return fx; }
}

void del(int x) {
	siz[fa[x]] -= siz[x];
	fa[x] = x;
}

void solve(int l, int r, int pos) {
	if(l == r) { if(siz[find(1)] == n) { cout << l; exit(0);} return ; }
	int mid = (l + r) >> 1;
	int tmp = pos, lsbl = 0;
	vector <int> v;
	for(; e[pos].w <= r && pos <= m; ++ pos) if((e[pos].w > mid) && (lsbl = unit(e[pos].u, e[pos].v))) v.push_back(lsbl);
	solve(l, mid, tmp);
	for(int i = v.size() - 1; i >= 0; -- i) del(v[i]); v.clear();
	pos = tmp, lsbl = 0;
	for(; e[pos].w <= mid && pos <= m; ++ pos) if(lsbl = unit(e[pos].u, e[pos].v)) v.push_back(lsbl);
	solve(mid + 1, r, pos);
	for(int i = v.size() - 1; i >= 0; -- i) del(v[i]); v.clear();
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++ i) fa[i] = i, siz[i] = 1;
	for(int i = 1; i <= m; ++ i) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
	sort(e + 1, e + 1 + m);
	solve(0, e[m].w + 1, 1);
	return 0;
}