RT

虽然在洛谷上过了这道题，但学校 OJ 上有一组 Hack 数据，且我挂了，求调错。

Code:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define int long long
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
	return x * f;
}
const int N = 100010;
int n, m, tot, fa[N], sum, ans = 0x7fffffffffffffff;
struct S{ int LCA, MAX, CMAX; };
struct node{
	int u, v, w;
	bool operator < (const node&rhs)const{
		return w < rhs.w;
	}
}a[N * 3];
inline int anc(int x){
	return x == fa[x] ? x : fa[x] = anc(fa[x]);
}
struct edge{
	int v, w, nxt;
}e[N << 1];
int head[N << 1], cnt, dep[N], f[N][20], g[N][20][2];
bool vis[N * 3];
inline void add(int u, int v, int w){
	e[++cnt].v = v;
	e[cnt].w = w;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}
inline void dfs(int u){
	for(int i = head[u]; i; i = e[i].nxt){
		int v = e[i].v, w = e[i].w;
		if(dep[v]) continue;
		dep[v] = dep[u] + 1;
		f[v][0] = u;
		g[v][0][0] = w;
		g[v][0][1] = -0x7f7f7f7f7f7f7f7f;
		for(int j = 1; j <= 17; ++j){
			f[v][j] = f[f[v][j - 1]][j - 1];
			if(g[v][j - 1][0] == g[f[v][j - 1]][j - 1][0]) g[v][j][1] = max(g[v][j - 1][1], g[f[v][j - 1]][j - 1][1]);
			if(g[v][j - 1][0] > g[f[v][j - 1]][j - 1][0]) g[v][j][1] = max(g[v][j - 1][1], g[f[v][j - 1]][j - 1][0]);
			if(g[v][j - 1][0] < g[f[v][j - 1]][j - 1][0]) g[v][j][1] = max(g[v][j - 1][0], g[f[v][j - 1]][j - 1][1]);
			g[v][j][0] = max(g[v][j - 1][0], g[f[v][j - 1]][j - 1][0]);
		}
		dfs(v);
	}
}
inline S lca(int a, int b){
	if(dep[a] < dep[b]) a ^= b ^= a ^= b;
	int ans1 = -0x7fffffffffffffff, ans2 = -0x7fffffffffffffff;
	for(int i = 17; i >= 0; --i) if(dep[f[a][i]] >= dep[b]){
		if(ans1 == g[a][i][0]) ans2 = max(ans2, g[a][i][1]);
		if(ans1 > g[a][i][0]) ans2 = max(ans2, g[a][i][0]);
		if(ans1 < g[a][i][0]) ans2 = max(ans1, g[a][i][1]);
		ans1 = max(ans1, g[a][i][0]);
		a = f[a][i];
	}
	if(a == b) return (S){a, ans1, ans2};
	for(int i = 17; i >= 0; --i) if(f[a][i] != f[b][i]){
		if(ans1 == g[a][i][0]) ans2 = max(ans2, g[a][i][1]);
		if(ans1 > g[a][i][0]) ans2 = max(ans2, g[a][i][0]);
		if(ans1 < g[a][i][0]) ans2 = max(ans1, g[a][i][1]);
		ans1 = max(ans1, g[a][i][0]);
		a = f[a][i];
		if(ans1 == g[b][i][0]) ans2 = max(ans2, g[b][i][1]);
		if(ans1 > g[b][i][0]) ans2 = max(ans2, g[b][i][0]);
		if(ans1 < g[b][i][0]) ans2 = max(ans1, g[b][i][1]);
		ans1 = max(ans1, g[b][i][0]);
		b = f[b][i];
	}
	if(ans1 == g[a][0][0]) ans2 = max(ans2, g[a][0][1]);
	if(ans1 > g[a][0][0]) ans2 = max(ans2, g[a][0][0]);
	if(ans1 < g[a][0][0]) ans2 = max(ans1, g[a][0][1]);
	ans1 = max(ans1, g[a][0][0]);
	return (S){f[a][0], ans1, ans2};
}
signed main(){
	n = read(); m = read();
	for(int i = 1; i <= m; ++i) a[i].u = read(), a[i].v = read(), a[i].w = read();
	for(int i = 1; i <= n; ++i) fa[i] = i;
	sort(a + 1, a + m + 1);
	for(int i = 1; i <= m; ++i){
		int u = a[i].u, v = a[i].v, w = a[i].w;
		if(anc(u) != anc(v)){
			vis[i] = 1;
			fa[fa[u]] = fa[v];
			add(u, v, w); add(v, u, w);
			sum += w; tot++;
			if(tot == n - 1) break;
		}
	}
	dfs(dep[1] = 1);
	for(int i = 1; i <= m; ++i){
		if(!vis[i]){
			int u = a[i].u, v = a[i].v, w = a[i].w;
			if(u == v) continue;
			S tmp = lca(u, v);
			int x = tmp.MAX, y = tmp.CMAX;
			if(x == w) ans = min(ans, sum - y + w);
			else ans = min(ans, sum - x + w);
		}
	}
	printf("%lld\n", ans);
	return 0;
}

做过的人应该都看得懂吧……

Input

Output