[NOIp2015] 信息传递 题解
2021/8/20 6:07:42
本文主要是介绍[NOIp2015] 信息传递 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
补题计划开始。
题目描述
求一个有向图的最小环。该图所有点的出度均为 \(1\)。
数据范围:\(1\le n\le 2 \times 10^5\) 。
误区
被样例误导,以为该图一定是连通的,于是认为整个图只有一个环,然后利用该性质进行解题。
错误代码很简单,就是找到唯一的环然后计算长度,容易误以为是正解实际只有 \(40 \text{pts}\) 。
碰到这种错误就 remake 吧。
解法
一个做法是 dfs 染色,这种做法很契合题目的出题意图,我特别想写这种做法但是写挂了。
考虑并查集求最小环。每一次都要判断两点间是否有边。无边则连上,有边则更新最小环大小。
如果有两个点祖先节点相同,那么就可以构成一个环,长度为两个点到祖先节点长度之和加 \(1\)。
代码实现
要直接在并查集上面改哦。具体的看代码。
代码
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int maxn = 200005; const int inf = 0x7fffffff; int n, a[maxn]; int f[maxn], d[maxn]; // f 保存祖先节点,d 保存到其祖先节点的路径长 int minn = inf; int find(int x) { if (f[x] != x) { int last = f[x]; f[x] = find(f[x]); d[x] += d[last]; } return f[x]; } void check(int a,int b) { int x = find(a), y = find(b); if (x != y) { f[x] = y; d[a] = d[b] + 1; } else minn = min(minn, d[a] + d[b] + 1); return; } int main() { cin >> n; for(int i = 1; i <= n; i ++) f[i] = i; for(int i = 1; i <= n; i ++) { int t; cin >> t; check(i, t); } cout << minn << endl; }
这篇关于[NOIp2015] 信息传递 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)