次小生成树

题目描述

思路

代码

#include <cstdio>
#include <algorithm>
#define max std::max
#define min std::min
#define swap std::swap
#define sort std::sort

const int MAX = 3e5 + 5, MAX_N = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int n, m;
int head[MAX_N], ver[MAX << 2], edge[MAX << 2], nt[MAX << 2], ht;
int fa[MAX_N]; // 并查集
int f[MAX_N][21], dep[MAX_N], g[MAX_N][21][2];
long long ans, ans_t = 0x3f3f3f3f3f3f3f3f;
struct Edge {
	int a, b, c;
	bool d;
} eg[MAX];
struct Res {
	int a, b;
} rs;
inline int read() {
	int s = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s;
}

void add(int x, int y, int z) {
	nt[++ht] = head[x], head[x] = ht, ver[ht] = y, edge[ht] = z;
}

int cmp(Edge a, Edge b) {
	return a.c < b.c;
}

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

void kruskal() {
	for (int i = 1; i <= n; ++i) fa[i] = i;
	sort(eg + 1, eg + m + 1, cmp);
	for (int i = 1, j = 0, a, b, c, ffa, ffb; i <= m; ++i) {
		a = eg[i].a, b = eg[i].b, c = eg[i].c;
		ffa = get(a), ffb = get(b);
		if (ffa != ffb) {
			ans += eg[i].c;
			fa[ffa] = ffb;
			eg[i].d = true;
			add(a, b, c), add(b, a, c);
			j++;
			if (j == n - 1) break;
		}
	}
}

void dfs_lca(int x, int y, int z) {
	dep[x] = dep[y] + 1;
	f[x][0] = y;
	g[x][0][0] = z;
	g[x][0][1] = -inf;
	for (int i = 1, a0, a1, b0, b1; i < 21; ++i) {
		f[x][i] = f[f[x][i - 1]][i - 1];
		a0 = g[x][i - 1][0], b0 = g[f[x][i - 1]][i - 1][0];
		a1 = g[x][i - 1][1], b1 = g[f[x][i - 1]][i - 1][1];
		g[x][i][0] = max(a0, b0);
		if (a0 == b0) g[x][i][1] = max(a1, b1);
		else if (a0 > b0) g[x][i][1] = max(b0, a1);
		else g[x][i][1] = max(a0, b1);
	}
	for (int i = head[x], j, k; i; i = nt[i]) {
		j = ver[i], k = edge[i];
		if (j == y) continue;
		dfs_lca(j, x, k);
	}
}

void modify(int a, int b) {
	if (rs.a == a) rs.b = max(rs.b, b);
	else if (rs.a > a) rs.b = max(a, rs.b);
	else rs.b = max(rs.a, b);
	rs.a = max(rs.a, a);
}

void lca(int x, int y) {
	rs.a = -inf, rs.b = -inf;
	if (dep[x] < dep[y]) swap(x, y);
	for (int i = 20; i >= 0; --i) {
		if (dep[f[x][i]] >= dep[y]) {
			modify(g[x][i][0], g[x][i][1]);
			x = f[x][i];
		}
	}
	if (x == y) return ;
	for (int i = 20; i >= 0; --i) {
		if (f[x][i] != f[y][i]) {
			modify(g[x][i][0], g[x][i][1]);
			modify(g[y][i][0], g[y][i][1]);
			x = f[x][i], y = f[y][i];
		}
	}
	modify(g[x][0][0], g[x][0][1]);
	modify(g[y][0][0], g[y][0][1]);
}


int main() {
	n = read(), m = read();
	for (int i = 1, a, b, c; i <= m; ++i) {
		a = read(), b = read(), c = read();
		eg[i].a = a, eg[i].b = b, eg[i].c = c;
	}
	kruskal();
	dfs_lca(1, 0, 0);
	// printf("%lld
", ans);

	for (int i = 1, a, b, c, d, lc; i <= m; ++i) {
		if (!eg[i].d) {
			lca(eg[i].a, eg[i].b);
			// printf("%d %d
", rs.a, rs.b);
			if (eg[i].c > rs.a) 
				ans_t = min(ans_t, ans - rs.a + eg[i].c);
			else if (eg[i].c == rs.a) 
				ans_t = min(ans_t, ans - rs.b + eg[i].c);
		}
	}
	printf("%lld
", ans_t);
	return 0;
}