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

题解:P1196 [NOI2002] 银河英雄传说

P1196 [NOI2002] 银河英雄传说

这是一道绿题
核心考察点只有一个: 那就是带权并查集


\(\mathcal{Part\ I}\)

我们检查题意不难发现这道题的要求无非两个:
$\ \ $ 1 ) 维护多个链的不断合并,但是以链中某节点作为索引
$\ \ \ \ \ \ \ $ 所以我们考虑并查集
$\ \ $ 2 ) 查询两个节点是否在某个链中,并且求出他们之间的权值差
$\ \ \ \ \ \ \ $ 因为要查询权值,而且并查集没有什么很好的伴生算法,只能使用带权并查集


\(\mathcal{Part\ II}\)

实现过程的话。。。其实就是标程
讲一遍吧(
$\ $
初始化并查集,这里分两步:

合并的时候,我们把第一集合的祖先的祖先插到第二集合的祖先上
这时关键的点在于不用更新每一个第一集合的点
我们退而求其次,只更新第一集合原祖先到队头的距离和当前总集合的大小
最后因为还要路径压缩,在路径压缩的时候顺下来就好了


查询的时候,我们查询的时候因为也要调用find函数两次,所以也可以帮忙顺一遍并查集的权值
这里的代码框架的好处就在于,不管我们要进行哪些操作,我们的更新写在find里,导致我们不用担心合并-查询的数据崭新度
而我们查询的操作极其简单,查询两个节点的祖先是否在同一个
如果不是,输出 -1
如果是,那么输出他们两个在链上的权值差-1就好了,这个-1是因为要计算他们之间隔了多少个

非常愉快,这个代码就写完了
我这边单独把 find 贴出来方便理解


int Find(int x) {if (x == fa[x]) return x; //回溯操作int k = fa[x]; //临时变量fa[x] = Find(fa[x]); //路径压缩s[x] += s[k]; //更新权值大小b[x] = b[fa[x]]; //更新集合大小return fa[x]; //传递
}

\(\LARGE{\mathcal{CODE}}\)


#include <bits/stdc++.h>using namespace std;const int N = 3e4 + 10;
int T, fa[N], s[N], b[N];int Find(int x) {if (x == fa[x]) return x;int k = fa[x];fa[x] = Find(fa[x]);s[x] += s[k];b[x] = b[fa[x]];return fa[x];
}void SolveM() {int x, y;cin >> x >> y;int dx = Find(x);int dy = Find(y);fa[dx] = dy;s[dx] += b[dy];b[dx] = b[dy] = b[dy] + b[dx];
}void SolveC() {int x, y;cin >> x >> y;int dx = Find(x);int dy = Find(y);if (dx != dy) {cout << "-1" << endl;return;}cout << abs(s[x] - s[y]) - 1 << endl;
}int main() {ios::sync_with_stdio(false);    cin.tie(nullptr);cout.tie(nullptr);cin >> T;for (int i = 1; i <= 30000; i++) {fa[i] = i;s[i] = 0;b[i] = 1;}while (T--) {char ch;cin >> ch;if (ch == 'M') {SolveM();}if (ch == 'C') {SolveC();}}return 0;
}
http://www.hskmm.com/?act=detail&tid=35875

相关文章:

  • Oracle下查询数据库SQL ID
  • 进程管理专题(一)
  • 使用SemaphoreSlim控制并发数
  • 杂题简述
  • css网格布局
  • 2025 年粘合剂厂家最新推荐排行榜:聚焦企业助力工业选品冷压球团/除尘灰/萤石粉/型煤/煤球粘合剂厂家推荐
  • 2025年流量控制阀厂家推荐排行榜,液压流量控制阀,气动流量控制阀,高压流量控制阀,精密流量控制阀批发公司推荐
  • 楼里网站开发完成,产品进入交代期
  • 比特币挖矿盈利能力9月下降超7%
  • 2025年医药冷链运输厂家权威推荐榜:药品/临床样本/CAR-T/蛋白/诊断试剂/生物制品/血液/细胞/芯片全程温控,冷藏车/冷藏箱/保温箱/干冰/液氮及国际冷链进出口专业服务
  • 2025 装修公司推荐排行榜单:江苏/浙江/制药厂/厂房/实验室/办公室/店面/净化室装修公司推荐,实测老客复购率与专业能力
  • 零代码改造 + 全链路追踪!Spring AI 最新可观测性详细解读
  • xupt 3g移动开发实验室二面
  • 2025年服饰厂家权威推荐榜:棒球帽,卫衣,羽绒服源头厂家精选,潮流设计与舒适品质口碑之选
  • 2025年10月北京昌平回龙观酒店推荐:对比评测榜助您锁定高性价比会议与度假之选
  • 2025年10月北京昌平回龙观酒店推荐榜:五家对比评测与实用选择指南
  • 2025 年最新华侨生联考培训机构口碑推荐榜:聚焦优质教学服务,助力考生高效备考,附详细选择指南
  • 洛谷题单指南-进阶数论-CF632D Longest Subsequence
  • 2025 年最新推荐锯床实力厂家排行榜:龙门 / 数控 / 金属带锯床等多类型设备权威甄选优质企业角度/金属带/双立柱/小型/大型锯床厂家推荐
  • 2025织带厂家权威推荐:东莞永沣专业定制防水织带与飞织鞋面
  • 2025发电机厂家实力推荐:三澳新能源科技专业制造,高效稳定动力解决方案
  • 2025年织带类厂家权威推荐榜:防水织带、鞋垫、编织包/针织包/飞织包包、松紧带、鞋带、织带、飞织鞋面源头企业精选
  • 2025年10月护眼台灯品牌评测推荐:十强榜单对比与理性选购指南
  • UV紫外相机在工业视觉检测中的应用 - 实践
  • 结对项目——实现一个自动生成小学四则运算题目的命令行程序
  • 2025 年最新推荐销轴厂家排行榜:含 8.8 级 / 4.8 级 / 10.9 级 / 镀锌 / 高强度 / 发黑 / 异型 / 非标 / 农机销轴公司推荐
  • 补贴防薅测试用例设计
  • 20232313 2025-2026-1 《网络与系统攻防技术》实验二实验报告 - 20232313
  • 2025 年电缆桥架生产厂家最新推荐排行榜:聚焦北方 / 河北区域及瓦楞 / 防火 / 模压 / 镀锌桥架优质品牌深度解析
  • 理解C++20的革命特性——协程支持2:编写简单的协程调度器 - 实践