P4180 [BJWC2010] 严格次小生成树-526互联

P4180 [BJWC2010] 严格次小生成树
/*
建立一个最小生成树 
维护最大值和严格次小值
然后直接查询就可以了 

5 6
1 2 1 
1 3 2 
2 4 3 
3 5 4 
3 4 3 
4 5 6 

*/

#include <bits/stdc++.h>
using namespace std;
#define int long long
using pii=pair<int,int>;
const int N=1e5+5;

int n,m,ans;
vector<array<int,4>>v;
int h[N],ne[N<<1],e[N<<1],w[N<<1],tot;
int fa[N];
int f[N][21],mx[N][21],mn[N][21],dep[N];

void add(int from,int to,int wi) {
	e[++tot]=to; w[tot]=wi; ne[tot]=h[from]; h[from]=tot;
} 

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

void kruskal() {
	sort(v.begin(),v.end());
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=0;i<v.size();i++) {
		int x=v[i][1],y=v[i][2],wi=v[i][0];
		int fx=find(x),fy=find(y);
		if(fx==fy)continue;
		fa[fx]=fy;
		ans+=wi;
		v[i][3]=1;
		add(x,y,wi);
		add(y,x,wi);
	}
}

void dfs(int x,int fa) {
	dep[x] = dep[f[x][0]] + 1;
	for(int i = 1; i <= 20; i++) {
		f[x][i] = f[f[x][i - 1]][i - 1];
		if(mx[x][i - 1] == mx[f[x][i - 1]][i - 1]) {
			mx[x][i] = mx[x][i - 1];
			mn[x][i] = max(mn[f[x][i - 1]][i - 1], mn[x][i - 1]);
		}
		if(mx[x][i - 1] > mx[f[x][i - 1]][i - 1]) {
			mx[x][i] = mx[x][i - 1];
			mn[x][i] = max(mx[f[x][i - 1]][i - 1], mn[x][i - 1]);
		}
		if(mx[x][i - 1] < mx[f[x][i - 1]][i - 1]) {
			mx[x][i] = mx[f[x][i - 1]][i - 1];
			mn[x][i] = max(mx[x][i - 1], mn[f[x][i - 1]][i - 1]);
		}
	}
	for(int i=h[x];i;i=ne[i]) {
		int y = e[i];
		if(y == f[x][0]) continue;
		f[y][0] = x; mx[y][0] = w[i];
		dfs(y,x);
	}
}

int LCA(int x,int y) {
	if(dep[x]<dep[y])swap(x,y);
	for(int i=20;i>=0;i--) {
		if(dep[f[x][i]]>=dep[y])x=f[x][i];
	}
	if(x==y)return x;
	for(int i=20;i>=0;i--) {
		if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
	}
	return f[x][0];
}

int find(int x,int y,int wi) {
	int lca = LCA(x, y);
	int numx = 0; int numm = 0;
	for(int i = 20; i >= 0; i--) {
		if(dep[f[x][i]] >= dep[lca]) {
			if(numx == mx[x][i]) numm = max(numm, mn[x][i]);
			if(numx > mx[x][i]) numm = max(numm, mx[x][i]);
			if(numx < mx[x][i]) 
				numm = max(numx, mn[x][i]), numx = mx[x][i] ;
			x = f[x][i];
		}
		if(dep[f[y][i]] >= dep[lca]) {
			if(numx == mx[y][i]) numm = max(numm, mn[y][i]);
			if(numx > mx[y][i]) numm = max(numm, mx[y][i]);
			if(numx < mx[y][i]) 
				numm = max(numx, mn[y][i]), numx = mx[y][i];
			y = f[y][i];
		}
	}
	//cout<<numx<<' '<<numm<<' '<<wi<<endl;
	if(wi != numx&&numx) return ans - numx + wi;
	else if(numm) return ans - numm + wi;
	else return 1e18;
}

void solve() {
	cin>>n>>m;
	for(int i=1;i<=m;i++) {
		int x,y,wi;
		cin>>x>>y>>wi;
		v.push_back({wi,x,y,0});
	}
	kruskal();
	dfs(1,0);
	//cout<<ans<<endl;
	int res=1e16;
	for(int i=0;i<v.size();i++) {
		if(v[i][3])continue;
		res=min(res,find(v[i][1],v[i][2],v[i][0]));
	}
	cout<<res<<endl;
}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	solve();
	return 0;
}
小生
P4180