EZOJ #386 最小生成树
2024-09-05 16:06:14
分析
先建出最小生成树
之后每次倍增找环即可
代码
#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 ;
}
最新文章
- 把java对象转化为json格式的对象数组
- 如何在win7系统中安装redis
- 【SpringBoot】SpringBoot 入门示例
- easyui怎样实现textarea
- Flyweight
- 读javascript高级程序设计02-变量作用域
- 第五周PSP
- PHP 魔术引号
- The entity type <;type>; is not part of the model for the current context
- PHP 开发 APP 接口 学习笔记与总结 - APP 接口实例 [4] 首页 APP 接口开发方案 ③ 定时读取缓存方式
- Navicat
- leetcode@ [97] Interleaving Strings
- 初识cocos2d-x-从环境配置到整体框架
- 从苹果的appstore谈谈web前端那丝毫的追求
- [Android FrameWork 6.0源码学习] View的重绘过程
- CSS多行文字超出隐藏加省略号
- Lingo求解线性规划案例2——多阶段投资问题
- luogu P4173 残缺的字符串
- 廖雪峰Java7处理日期和时间-4最佳实践-最佳实践
- 在 Ubuntu 16.04上安装 vsFTPd
热门文章
- vue登录注册实践
- docker--虚拟化
- Java相关面试题总结+答案(五)
- Lucene 4.6.1 java.lang.IllegalStateException: TokenStream contract violation
- utf-8 bom头问题 thinkphp 报错 Namespace declaration statement has to be the very first statement in the script
- 小白学Python(13)——pyecharts 绘制 柱状图/条形图 Bar
- C	Yuhao and a Parenthesis
- apache2.4 只允许合法域名访问网站 禁止使用ip、非法域名访问
- 原生JS实现图片循环切换
- MYSQL学习笔记——常用语句