求调
查看原帖
求调
982056
liyp楼主2025/7/24 15:57
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
int n,m;
vector<pair<int,int> >v[MAXN];
struct edge{
	int x;int y;int w;
};
edge edges[MAXN];

struct S{
	int u,d;
};
bool operator<(const S &x, const S &y) {return x.d>y.d;}

#define TP q.top()

priority_queue<S>q;
int dis[MAXN],cnt=0,res=0;
bool vis[MAXN];
int from[MAXN];
void Prim(){
	memset(dis,0x3f,size(dis));
	dis[1]=0;
	q.push({1,0});
	while(!q.empty()){
		if(cnt>=n) break;
		int u=TP.u,d=TP.d;
		q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		++cnt;
		res+=d;
		for(auto i:v[u]){
			int v=i.first,w=i.second;
			if(w<dis[v]){
				from[v]=u;
				dis[v]=w;q.push({v,w});
			}
		}
	}
}
int f[MAXN][30],deep[MAXN];
void dfs1(int x,int fa){
	deep[x]=deep[fa]+1;
	f[x][0]=fa;
//	cout<<x;
	for(auto i:v[x]){
		int v=i.first;
		if(v==fa) continue;
		if(from[v]==x)dfs1(v,x);
	}
}
int LCA(int x,int y){
	if(deep[x]<deep[y]) swap(x,y);
	int delta_deep=deep[x]-deep[y];
	for(int j=22;j>=0;j--)
		if((delta_deep>>j)&1) x=f[x][j];
	if(x==y) return x;
	for(int j=22;j>=0;j--)
	{
		if(f[x][j]==f[y][j]) continue;
		x=f[x][j],y=f[y][j];
	}
	return f[x][0];
}
unordered_map<int,unordered_map<int,bool> >mp;
signed main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1,u,t,w;i<=m;i++){
		cin>>u>>t>>w;
		v[u].push_back({t,w});
		v[t].push_back({u,w});
		edges[i].w=w;
		edges[i].x=u;
		edges[i].y=t;
	}
	Prim();
	
	for(int i=2;i<=n;i++){
		mp[i][from[i]]=1;
		mp[from[i]][i]=1;
	}
	for(int i=1;i<=n;i++){
		f[i][0]=from[i];
	}
	for(int j=1;j<=22;j++)
		for(int i=1;i<=n<<1;i++){
			f[i][j]=f[f[i][j-1]][j-1];
		}
	deep[1]=1;
	
	dfs1(1,0);
//	cout<<1;
//	cout<<res;
	for(int i=1;i<=m;i++){
		if(mp[edges[i].x][edges[i].y]==1){
			cout<<res<<endl;
		}
		else{
			int t=LCA(edges[i].x,edges[i].y);
//			cout<<t;
			cout<<res-dis[t]+edges[i].w<<endl;
		}
	}
	return 0;
}
2025/7/24 15:57
加载中...