分析

先建出最小生成树

之后每次倍增找环即可

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node {
int x,y,z,is,id;
};
node d[];
int head[],nxt[],to[],w[],cnt,res,dep[];
int pr[][],sum[][],n,m,ans[],fa[],tot;
inline void add(int x,int y,int z){
nxt[++cnt]=head[x];
head[x]=cnt;
to[cnt]=y;
w[cnt]=z;
nxt[++cnt]=head[y];
head[y]=cnt;
to[cnt]=x;
w[cnt]=z;
}
inline void dfs(int x,int fa){
dep[x]=dep[fa]+;
pr[x][]=fa;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=fa)sum[to[i]][]=w[i],dfs(to[i],x);
}
inline int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
int len=dep[x]-dep[y],wh=;
for(int i=;i<=;i++)
if((<<i)&len)wh=max(wh,sum[x][i]),x=pr[x][i];
if(x==y)return wh;
for(int i=;i>=;i--)
if(pr[x][i]!=pr[y][i]){
wh=max(wh,max(sum[x][i],sum[y][i]));
x=pr[x][i];
y=pr[y][i];
}
wh=max(wh,max(sum[x][],sum[y][]));
return wh;
}
inline bool cmp(const node a,const node b){return a.z<b.z;}
inline int sf(int x){return fa[x]==x?x:fa[x]=sf(fa[x]);}
signed main(){
int i,j,k;
scanf("%lld%lld",&n,&m);
for(i=;i<=m;i++){
scanf("%lld%lld%lld",&d[i].x,&d[i].y,&d[i].z);
d[i].id=i;
}
for(i=;i<=n;i++)fa[i]=i;
sort(d+,d+m+,cmp);
for(i=;i<=m;i++){
int x=d[i].x,y=d[i].y;
if(sf(x)==sf(y))continue;
fa[sf(y)]=sf(x);
add(x,y,d[i].z);
res+=d[i].z;
tot++;
d[i].is=;
if(tot==n-)break;
}
dfs(,);
for(i=;i<=;i++)
for(j=;j<=n;j++)
pr[j][i]=pr[pr[j][i-]][i-],
sum[j][i]=max(sum[j][i-],sum[pr[j][i-]][i-]);
for(i=;i<=m;i++){
if(d[i].is)ans[d[i].id]=res;
else ans[d[i].id]=res+d[i].z-lca(d[i].x,d[i].y);
}
for(i=;i<=m;i++)printf("%lld\n",ans[i]);
return ;
}

最新文章

  1. 把java对象转化为json格式的对象数组
  2. 如何在win7系统中安装redis
  3. 【SpringBoot】SpringBoot 入门示例
  4. easyui怎样实现textarea
  5. Flyweight
  6. 读javascript高级程序设计02-变量作用域
  7. 第五周PSP
  8. PHP 魔术引号
  9. The entity type &lt;type&gt; is not part of the model for the current context
  10. PHP 开发 APP 接口 学习笔记与总结 - APP 接口实例 [4] 首页 APP 接口开发方案 ③ 定时读取缓存方式
  11. Navicat
  12. leetcode@ [97] Interleaving Strings
  13. 初识cocos2d-x-从环境配置到整体框架
  14. 从苹果的appstore谈谈web前端那丝毫的追求
  15. [Android FrameWork 6.0源码学习] View的重绘过程
  16. CSS多行文字超出隐藏加省略号
  17. Lingo求解线性规划案例2——多阶段投资问题
  18. luogu P4173 残缺的字符串
  19. 廖雪峰Java7处理日期和时间-4最佳实践-最佳实践
  20. 在 Ubuntu 16.04上安装 vsFTPd

热门文章

  1. vue登录注册实践
  2. docker--虚拟化
  3. Java相关面试题总结+答案(五)
  4. Lucene 4.6.1 java.lang.IllegalStateException: TokenStream contract violation
  5. utf-8 bom头问题 thinkphp 报错 Namespace declaration statement has to be the very first statement in the script
  6. 小白学Python(13)——pyecharts 绘制 柱状图/条形图 Bar
  7. C Yuhao and a Parenthesis
  8. apache2.4 只允许合法域名访问网站 禁止使用ip、非法域名访问
  9. 原生JS实现图片循环切换
  10. MYSQL学习笔记——常用语句