当前位置：首页 > backend >正文

【C++贪心图论】P7903兜心の顶|普及

backend 2025/7/1 23:16:05

本文涉及知识点

C++贪心
C++图论

兜心の顶

题目描述

给定正整数 $n$ ，要求构造一棵 $n$ 个结点的树，满足树的直径的重心不是树的重心。
同时这棵树需满足：直径 $^1$ 、重心 $^2$ 、直径的重心 $^3$ 全部唯一。

注：

输入格式

第一行输入一个正整数 $n$ ，表示树的结点个数。

输出格式

第一行输出一个正整数 $n$ 。
接下来 $n - 1$ 行，每行输出两个正整数 $u, v$ ，表示树的一条边。
无解输出 -1。
本题采取 Special Judge，输出任意一组合法解均给分。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

-1

提示

样例说明

样例 #1 中直径的重心是 $7$ ，树的重心是 $1$ ， $1\ne7$ 。

样例 #2 中 $n = 2$ ，只有两个点时显然重心不可能唯一。

数据范围

本题采取捆绑测试。

子任务编号	分值	特殊性质
$1$	$30$	$n\le10$
$2$	$30$	$n$ 是奇数
$3$	$30$	$n$ 是偶数
$4$	$10$	无

对于 $100\%$ 的数据： $1\le n\le10^4$ 。

贪心+图论

性质一：树的直径d一定是偶数，否则树的直径一定有两个重心。半径r = d/2。
性质二：令树的直径两个端点是n1,n2，n1和n2相邻的点是n3和n4，直径的中心是o。n1和n3不能和新点n5连接，否则n5和n2是新的直径。
性质三：令某新点n5到距离直径最近的点是o，则n5的距离必须小于等于r，否则n5n2是新直接。
结论一：r为1，不能增加任何和直径直接相连的点。
结论二：r为2，只能增加和o直接相邻的点。o必定是树的重心。和本题不符合。
结论三：r为3，令和o直接相邻的点是n5,n6。n5增加一个直接相邻的点后，树就有两个重心：o和n5，n5增加两个直接相邻的节点后。重心就转移到n5。
故符合题意的树，至少9个节点。
结论四：多的节点都和n5相邻。即 n >=9 一定有解；n < 9，无解。
其它： r为3是,n7连o，其它连n7也可以。只是需要更多节点。r >3是，至少需要9个节点，故不会优于当前解。
解法：
n < 9 返回-1。否则：
i和i+1相邻，i $\in$ [1,6]。[7,n]全部和5相连。

代码

核心代码

	class Solution {public:vector<pair<int, int>> MinMS(int n) {if (n < 9) { return {}; }int i = 1;vector<pair<int, int>> ans;for (; i <= 6; i++) { ans.emplace_back(i, i + 1); }for (i = 8; i <= n; i++) { ans.emplace_back(5, i); };return ans;}};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUGint n;scanf("%d", &n);auto res = Solution().MinMS(n);if (0 == res.size()) {printf("-1");}else {printf("%d\r\n", n);for (const auto& [i1, i2] : res) {printf("%d %d\r\n", i1, i2);}}return 0;
}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功