洛谷 P4180 【模板】严格次小生成树

题目链接

https://www.luogu.org/problem/P4180

分析

根据Kruskal算法的思想，（非）严格次小生成树应该是来自最小生成树的；

具体来说，是将某条非树边加入到MST上，再删去产生的环里原树边中边权最大的一条；

枚举加入的非树边，再用倍增算法求要删去的树边；

但要求严格次小生成树，所以删去的树边不可以和插入的边权值相等，

这样维护树上路径最大值的同时还要维护次大值。

AC代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

inline int read() {
	int num = 0;
	char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9')
		num = num * 10 + c - '0', c = getchar();
	return num;
}

const int maxn = 1e5 + 5, maxm = 3e5 + 5;

int head[maxn], eid;

struct Edge {
	int u, v, w, flag, next;

	bool operator < (const Edge& rhs) const {
		return w < rhs.w;
	}
} edge0[maxm], edge[2 * maxn];

inline void insert(int u, int v, int w) {
	edge[++eid].v = v;
	edge[eid].w = w;
	edge[eid].next = head[u];
	head[u] = eid;
}

int fa[maxn], depth[maxn], f[maxn][20], max1[maxn][20], max2[maxn][20];

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

void dfs(int u, int father) {
	for (int i = 1; (1 << i) <= depth[u]; ++i) {
		f[u][i] = f[f[u][i - 1]][i - 1];
		max1[u][i] = max(max1[u][i - 1], max1[f[u][i - 1]][i - 1]);
		if (max1[u][i - 1] == max1[f[u][i - 1]][i - 1])
			max2[u][i] = max(max2[u][i - 1], max2[f[u][i - 1]][i - 1]);
		else max2[u][i] = min(max1[u][i - 1], max1[f[u][i - 1]][i - 1]);
	}
	for (int p = head[u]; p; p = edge[p].next) {
		int v = edge[p].v, w = edge[p].w;
		if (v == father) continue;
		depth[v] = depth[u] + 1;
		f[v][0] = u, max1[v][0] = w;
		dfs(v, u);
	}
}

inline int lca(int x, int y) {
	if (depth[x] < depth[y]) swap(x, y);
	for (int i = 19; i >= 0; --i)
		if (depth[x] - (1 << i) >= depth[y]) x = f[x][i];
	if (x == y) return x;
	for (int i = 19; i >= 0; --i)
		if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0];
}

inline int get(int x, int y, int l) {
	int ret = 0;
	for (int i = 19; i >= 0; --i)
		if (depth[f[x][i]] >= depth[y]) {
			ret = max(ret, max1[x][i] == l ? max2[x][i] : max1[x][i]);
			x = f[x][i];
		}
	return ret;
}

int main() {
	int n = read(), m = read(), cnt = 0;
	long long sum = 0, ans = 1e18;
	for (int i = 1; i <= m; ++i) {
		edge0[i].u = read(), edge0[i].v = read(), edge0[i].w = read();
		edge0[i].flag = 0;
	}
	sort(edge0 + 1, edge0 + m + 1);
	for (int i = 1; i <= n; ++i) fa[i] = i;
	for (int i = 1; i <= m; ++i) {
		int u = edge0[i].u, v = edge0[i].v, w = edge0[i].w;
		if (find(u) != find(v)) {
			insert(u, v, w), insert(v, u, w);
			u = find(u), v = find(v);
			edge0[i].flag = 1, fa[u] = v, sum += w;
			if (++cnt > n - 1) break;
		}
	}
	memset(depth, -1, sizeof(depth));
	depth[1] = 0;
	dfs(1, 0);
	for (int i = 1; i <= m; ++i)
		if (!edge0[i].flag) {
			int x = edge0[i].u, y = edge0[i].v, z = edge0[i].w, l, d;
			l = lca(x, y), d = max(get(x, l, z), get(y, l, z));
			ans = min(ans, sum - d + z);
		}
	printf("%lld", ans);
	return 0;
}