当前位置: 首页 > news >正文

[题解]P11095 [ROI 2021] 旅行 (Day 2)

思路

对于 Subtask 2,本质是确定了最小值,要使 \(1 \leadsto u\) 路径上边权最大值最小,显然直接上 Kruskal 重构树。

Code

#include <bits/stdc++.h>
#define re register
#define fst first
#define snd second
#define chmin(a,b) (a = min(a,b))
#define chmax(a,b) (a = max(a,b))using namespace std;typedef pair<int,int> pii;
const int N = 3e5 + 10,M = N * 2;
const int inf = 2e9 + 10;
int n,m;
bool mark[N];
vector<int> S[N];
vector<pii> g[N];
int tim,fp[N],sz[N],dfn[N],pid[N],dep[N],ltm[N],val[N];struct edge{int u,v,w;bool friend operator <(const edge &a,const edge &b){ return a.w < b.w; }
}E[N];inline int read(){int r = 0,w = 1;char c = getchar();while (c < '0' || c > '9'){if (c == '-') w = -1;c = getchar();}while (c >= '0' && c <= '9'){r = (r << 3) + (r << 1) + (c ^ 48);c = getchar();}return r * w;
}struct{int fp[N];inline void init(int n){for (re int i = 1;i <= n;i++) fp[i] = i;}inline int find(int x){if (fp[x] == x) return fp[x];else return fp[x] = find(fp[x]);}inline void merge(int a,int b){int x = find(a),y = find(b);fp[x] = y;}
}D;inline void dfs(int u,int fa){dep[u] = dep[fp[u] = fa] + 1;sz[pid[dfn[u] = ++tim] = u] = 1;for (pii v:g[u]){if (v.fst == fa) continue;ltm[v.fst] = max(ltm[u],v.snd);val[v.fst] = min(val[u],E[v.snd].w);dfs(v.fst,u); sz[u] += sz[v.fst];}
}struct{#define ls(u) (u << 1)#define rs(u) (u << 1 | 1)#define mid (tr[u].l + tr[u].r >> 1)int typ;struct node{int l,r;int val,tag;}tr[N << 2];inline void calc(int u,int k){ chmin(tr[u].val,k); chmin(tr[u].tag,k); }inline void pushup(int u){ tr[u].val = min(tr[ls(u)].val,tr[rs(u)].val); }inline void pushdown(int u){if (tr[u].tag < inf){ calc(ls(u),tr[u].tag); calc(rs(u),tr[u].tag); }tr[u].tag = inf;}inline void build(int u,int l,int r){tr[u] = {l,r,inf,inf};if (l == r) return (tr[u].val = (!typ ? val[pid[l]] : inf)),void();build(ls(u),l,mid); build(rs(u),mid + 1,r);pushup(u);}inline void modify(int u,int x,int k){if (tr[u].l == tr[u].r) return (tr[u].val = k),void();pushdown(u);if (x <= mid) modify(ls(u),x,k);else modify(rs(u),x,k);pushup(u);}inline void update(int u,int l,int r,int k){if (l <= tr[u].l && tr[u].r <= r) return calc(u,k);pushdown(u);if (l <= mid) update(ls(u),l,r,k);if (r > mid) update(rs(u),l,r,k);pushup(u);}inline int query(int u,int x){if (tr[u].l == tr[u].r) return tr[u].val;pushdown(u);if (x <= mid) return query(ls(u),x);else return query(rs(u),x);}#undef ls#undef rs#undef mid
}T1,T2;int main(){n = read(),m = read();fill(val + 1,val + n + 1,inf);for (re int i = 1,u,v,w;i <= m;i++){u = read(),v = read(),w = read();E[i] = {u,v,w};} sort(E + 1,E + m + 1);D.init(n);for (re int i = 1,u,v;i <= m;i++){u = E[i].u,v = E[i].v;if (D.find(u) == D.find(v)) continue;g[u].push_back({v,i});g[v].push_back({u,i});mark[i] = true; D.merge(u,v);// cerr << u << " " << v << " " << E[i].w << " ???\n";} dfs(1,0); D.init(n);T1.typ = 0,T2.typ = 1;T1.build(1,1,n); T2.build(1,1,n);for (re int i = 1;i <= n;i++) S[ltm[i]].push_back(i);for (re int i = 1,u,v,w;i <= m;i++){u = E[i].u,v = E[i].v,w = E[i].w;if (mark[i]){for (int x:S[i]) T2.modify(1,dfn[x],T1.query(1,dfn[x]) + w);}else{int x = D.find(u),y = D.find(v);if (x == y) continue;while (x != y){if (dep[x] < dep[y]) swap(x,y);int fa = D.find(fp[x]);chmin(val[fa],val[x]);D.merge(x,fa); x = fa;}T1.update(1,dfn[x],dfn[x] + sz[x] - 1,val[x]);T2.update(1,dfn[x],dfn[x] + sz[x] - 1,val[x] + w);}}for (re int i = 2;i <= n;i++) printf("%d\n",T2.query(1,dfn[i]));return 0;
}
http://www.hskmm.com/?act=detail&tid=11754

相关文章:

  • DDR5内存时序参数对照表
  • Linux CentOS 第三方扩展模块编译并安装
  • Java ArrayList中的常见删除操作及方法
  • ADC和GPIO的关系
  • 使用Docker Compose工具进行容器编排的教程
  • 模拟输入的过程
  • 基于Redisson和自定义注解的分布式锁实现策略
  • CCPC2025网络赛 游记
  • 知行合一
  • Manim实现水波纹特效
  • 深入解析:解锁AI智能体:上下文工程如何成为架构落地的“魔法钥匙”
  • JS之使用for...of赋值失败的原因分析
  • String
  • Linux /lib/modules/$(uname -r)/ 目录功能作用详解
  • 《建筑的永恒之道》第 27 章:道之核心
  • 软件工程第二次作业_个人项目
  • Linux命令大全(档案管理)
  • 小狼毫雾凇拼音安装部署
  • Chapter 3 Resize and Cropping
  • 详细介绍:java中常见的几种排序算法
  • 使用FFmpeg转换m4a
  • 提升多屏监控体验/新增辅屏预览功能/轻松实现跨屏实时监控/支持高达500路多个屏幕同时显示
  • [Java SE/文件系统/IO] 核心源码精讲:java.io.File
  • Linux 内核整体架构详解
  • atoi() - 字符串( ASCLL )转换为整数( int )
  • 02.Python:Flash初步使用
  • 解决Kubernetes集群中master节点无法与node节点通信的策略
  • 从高版本的sqlserver向低版本的sqlserver上复制表和数据的方法
  • 在Ubuntu18.04安装兼容JDK 8的Eclipse集成开发环境
  • 【php】带数组的文件列表生成,返回数组