求调
查看原帖
求调
601245
I_am_zhima楼主2023/7/21 18:49
#include<bits/stdc++.h>
using namespace std;
#define re register
#define int long long
const int N=1e6+5;

int n,m,ans;
struct node{int id,u,v,w;}t[N];

bool cmp1(node x,node y){return x.w<y.w;}
bool cmp2(node x,node y){return x.id<y.id;}

int fa[N];
struct edge{int v,w;};vector<edge> e[N];
int findx(int x){
	if(fa[x]==x)
		return x;
	return fa[x]=findx(x);
}
void kruskal(){
	sort(t+1,t+n+1,cmp1);
	for(re int i=1;i<=n;i++)
		fa[i]=i;
	for(re int i=1;i<=m;i++){
		int u=t[i].u,v=t[i].v,w=t[i].w;
		int fx=findx(u),fy=findx(v);
		if(fx!=fy){
			e[u].push_back({v,w});
			e[v].push_back({u,w});
			ans+=w;
		}
	}
}

int f[N][20],w[N][20],de[N];
int dfs(int u,int fath){
	de[u]=de[fath]+1,f[u][0]=fath,w[u][0]=e[u][fath].w;
	for(re int i=1;f[u][i-1];i++)
		f[u][i]=f[f[u][i-1]][i-1],w[u][i]=w[w[u][i-1]][i-1];
	
	for(auto i:e[u])
		if(i.v!=fath)
			dfs(i.v,u);
}
int lca(int u,int v){
	if(de[u]>de[v])
		swap(u,v);
	
	for(re int i=20;i>=0;i--)
		if(de[f[v][i]]>=de[u])
			v=f[v][i];
	
	if(u==v)
		return u;
	
	int sum=0;
	for(re int i=20;i>=0;i--)
		if(f[v][i]!=f[u][i]){
			v=f[v][i],u=f[u][i];
			sum=max(sum,max(w[u][i],w[v][i]));
		}
	return max(sum,max(w[u][0],w[v][0]));
}
signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	
	cin>>n>>m;
	for(re int i=1;i<=n;i++)
		cin>>t[i].u>>t[i].v>>t[i].w,t[i].id=i;
	
	kruskal(),dfs(1,0);
	
	sort(t+1,t+n+1,cmp2);
	for(re int i=1;i<=m;i++)
		cout<<ans-lca(t[i].u,t[i].v)+t[i].w<<"\n";
	
	return 0;
}
2023/7/21 18:49
加载中...