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

hetao 国庆

Day 5

T3

Solution

Subtask 1 可能比较具有启发性。

每个人只关心:每条路径上的最大值。我们要让这个值最小。所以容易发现他们只会在最小瓶颈树上走。

由于 MST 一定是最小瓶颈树,所以我们跑 kruskal 然后把树建出来。

此时边分为两类:

  • 非树边:
    • 考虑 \((u, v)\) 这条边,记 \(mx\) 为树上 \((u, v)\) 路径上边权的最大值。
      • 那么这条边的边权如果 \(< x\) 那么他就会代替树上的一条边。
      • 如果边权 \(= x\) 则他也可能成为树边。
    • 所以这条边的边权至少为 \(mx + 1\)
  • 树边:
    • 考虑我们可以有哪些边来替代这条树边 \((u, v)\)
      • 考虑添加一条非树边 \((u, v)\) 进来,则你可以把树上 \((u, v)\) 路径上的边随意删一个。
      • 所以这条边可以覆盖 \((u, v)\) 这条路径上的边。
    • 所以我们这条边的边权至少为可以覆盖到这条边的边边权的最小值。

那对于非树边你就可以树上倍增维护路径最大值。

对于树边你就可以按边权从大到小排序,然后树剖做区间覆盖。查询单点查就行。

Code

#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 10, inf = 0x3f3f3f3f;int n, m, p[N], dep[N], f[19][N], z[19][N], son[N], top[N], dfn[N], cnt, sz[N], ans[N];
struct edge { int u, v, w, id; bool ok; } e[N];
vector<pair<int, int>> g[N];void dfs(int u, int fa)
{dep[u] = dep[f[0][u] = fa] + 1;sz[u] = 1;for (auto t : g[u]) {int v = t.first, w = t.second;if (v == fa) continue;z[0][v] = w;dfs(v, u); sz[u] += sz[v];if (sz[v] > sz[son[u]]) son[u] = v;}
}void dfs1(int u, int t)
{top[u] = t;dfn[u] = ++cnt;if (son[u]) dfs1(son[u], t);for (auto k : g[u]) {int v = k.first;if (v != f[0][u] && v != son[u]) dfs1(v, v);}
}int lca(int x, int y)
{int ans = 0;if (dep[x] < dep[y]) swap(x, y);for (int i = 18; i >= 0; i--) if (dep[f[i][x]] >= dep[y]) ans = max(ans, z[i][x]), x = f[i][x];if (x == y) return ans;for (int i = 18; i >= 0; i--) {if (f[i][x] != f[i][y]) {ans = max(ans, max(z[i][x], z[i][y]));x = f[i][x], y = f[i][y];}}ans = max(ans, max(z[0][x], z[0][y]));return ans;
}int fifa(int x) { return p[x] == x ? p[x] : p[x] = fifa(p[x]); }bool merge(int x, int y)
{x = fifa(x), y = fifa(y);if (x == y) return false;p[x] = y;return true;
}int tr[N << 2], tag[N << 2];#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid (l + r) / 2void pushup(int rt) { tr[rt] = min(tr[ls], tr[rs]); }void pushdown(int rt)
{int &u = tag[rt];if (!u) return;tr[ls] = tr[rs] = tag[ls] = tag[rs] = u;u = 0;
}void update(int rt, int l, int r, int sp, int ep, int v)
{if (sp <= l && r <= ep) return tr[rt] = tag[rt] = v, void();pushdown(rt);if (sp <= mid) update(ls, l, mid, sp, ep, v);if (ep > mid) update(rs, mid + 1, r, sp, ep, v);pushup(rt);
}int query(int rt, int l, int r, int p)
{if (l == r) return tr[rt];pushdown(rt);if (p <= mid) return query(ls, l, mid, p);return query(rs, mid + 1, r, p);
}void addpath(int x, int y, int w)
{while (top[x] != top[y]) {if (dep[top[x]] < dep[top[y]]) swap(x, y);update(1, 1, n, dfn[top[x]], dfn[x], w);x = f[0][top[x]];}if (dfn[x] > dfn[y]) swap(x, y);update(1, 1, n, dfn[x] + 1, dfn[y], w);
}void kruskal()
{for (int i = 1; i <= n; i++) p[i] = i;sort (e + 1, e + m + 1, [&](edge x, edge y) { return x.w < y.w; });for (int i = 1; i <= m; i++) {int u = e[i].u, v = e[i].v, w = e[i].w;if (merge(u, v)) {e[i].ok = 1;g[u].emplace_back(v, w);g[v].emplace_back(u, w);}}
}int main()
{freopen("skyline.in", "r", stdin);freopen("skyline.out", "w", stdout);cin.tie(0)->ios::sync_with_stdio(false);cin >> n >> m;for (int i = 1; i <= m; i++) {int u, v, w; cin >> u >> v >> w;e[i] = (edge){ u, v, w, i, 0 };}kruskal();dfs(1, 0), dfs1(1, 1);for (int j = 1; j <= 18; j++)for (int i = 1; i <= n; i++) f[j][i] = f[j - 1][f[j - 1][i]], z[j][i] = max(z[j - 1][i], z[j - 1][f[j - 1][i]]);for (int i = 1; i <= 4 * n; i++) tr[i] = inf, tag[i] = 0;for (int i = m; i >= 1; i--) {if (e[i].ok) continue;addpath(e[i].u, e[i].v, e[i].w);}for (int i = 1; i <= m; i++) {if (e[i].ok) {ans[e[i].id] = query(1, 1, n, dfn[(dep[e[i].u] > dep[e[i].v] ? e[i].u : e[i].v)]);} else {ans[e[i].id] = lca(e[i].u, e[i].v);}}for (int i = 1; i <= m; i++) cout << (ans[i] == inf ? -1 : ans[i] + 1) << " ";return 0;
}
http://www.hskmm.com/?act=detail&tid=25482

相关文章:

  • 详细介绍:运维 pgsql 安装完后某次启动不了
  • visual studio
  • [MCP] StreamableHTTPServer
  • 牛客 周赛109 20250924
  • 罗技G102螺丝型号
  • 详细介绍:深入剖析C#构造函数执行:基类调用、初始化顺序与访问控制
  • 英语_阅读_Let your baby go_待读
  • 第三章习题
  • 系统管理员的日常困境与幽默自嘲
  • AI数据标注平台获融资挑战行业巨头
  • 详细介绍:如何用 pnpm patch 给 element-plus 打补丁修复线上 bug(以 2.4.4 修复 PR#15197 为例)
  • Numericaltables1
  • ARC 207
  • 半年小结 Vol4. 跌跌撞撞开启 PhD 生涯
  • 深入解析:C++:内存管理
  • 大数求余
  • visual studio 无法打开文件
  • 基于MPPT算法的光伏并网发电系统simulink建模与仿真
  • 实用指南:【系统架构设计师】2025年上半年真题论文回忆版: 论系统负载均衡设计方法(包括解题思路和参考素材)
  • 软件版悟空博弈+WAUC构筑元人文演化之路研究报告——声明Ai研究
  • QBXT2025S刷题 Day5题
  • [KaibaMath1001] 关于∀ε0,|a-b|ε = a=b的证明
  • 基于Web的分布式图集管理系统架构设计与实践 - 教程
  • TCP小结 - 指南
  • 国庆 Day2 强基物理
  • ZR 2025 十一集训 Day 6
  • 软件版悟空博弈 + WAUC:构筑元人文的演化之路
  • 基于MVO多元宇宙优化的DBSCAN聚类算法matlab仿真
  • AirSim 安装过程记录 - zzh
  • LARAVEL安装报错:Illuminate\Database\QueryException could not find driver (Connection: sqlite, SQL: