似乎被卡常了,求助
查看原帖
似乎被卡常了,求助
378346
expnoi楼主2023/3/13 14:43
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int s=0,w=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')w=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')s=(s<<3)+(s<<1)+(c^48),c=getchar();
	return s*w;
}
inline void print(int x)
{
	if(x<0)x=-x,putchar('-');
	if(x>=10)print(x/10);
	putchar(x%10+48);
}
int n,m,fa[1000010];
struct node{
	int u,v,w,id;
	bool operator<(const node &x)const
	{
		return w<x.w;
	}
}G[1000010];
inline int get(int x)
{
	return fa[x]==x?x:get(fa[x]);
}
struct edge{
	int v,w,next;
}e[1000010];
int eid=1,head[1000010],f[400010][20],w[400010][20],dep[400010],res,vis[400010],ans[400010];
inline void insert(int u,int v,int w)
{
	e[eid].v=v;
	e[eid].w=w;
	e[eid].next=head[u];
	head[u]=eid++;
}
inline void dfs(int u,int fa)
{
	f[u][0]=fa;
	dep[u]=dep[fa]+1;
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==fa)continue;
		w[v][0]=e[i].w;
		dfs(v,u);
	}
}
inline int Max(int a,int b)
{
	if(dep[a]<dep[b])swap(a,b);
	int ma=0;
	for(int i=19;i>=0;i--)
	{
		if(dep[f[a][i]]>=dep[b])ma=max(ma,w[a][i]),a=f[a][i];
	}
	if(a==b)return ma;
	for(int i=19;i>=0;i--)
	{
		if(f[a][i]!=f[b][i])
		{
			ma=max({ma,w[a][i],w[b][i]});
			a=f[a][i];
			b=f[b][i];
		}
	}
	return max({ma,w[a][0],w[b][0]});
}
signed main()
{
	n=read();
	m=read();
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read(),w=read();
		G[i]={u,v,w,i};
	}
	sort(G+1,G+m+1);
	for(int i=1;i<=m;i++)
	{
		int u=get(G[i].u),v=get(G[i].v);
		if(u!=v)
		{
			fa[u]=v;
			insert(G[i].u,G[i].v,G[i].w);
			insert(G[i].v,G[i].u,G[i].w);
			res+=G[i].w;
			vis[i]=1;
		}
	}
	dfs(1,0);
	for(int j=1;j<=19;j++)
	{
		for(int i=1;i<=n;i++)
		{
			f[i][j]=f[f[i][j-1]][j-1];
			w[i][j]=max(w[i][j-1],w[f[i][j-1]][j-1]);
		}
	}
	for(int i=1;i<=m;i++)
	{
		if(vis[i])
		{
			ans[G[i].id]=res;
			continue;
		}
		int a=G[i].u,b=G[i].v,c=G[i].w;
		int ma=Max(a,b);
		ans[G[i].id]=res-ma+c;
	}
	for(int i=1;i<=m;i++){
		print(ans[i]);
		puts("");
	}
}
2023/3/13 14:43
加载中...