A789（翻译）
2025-12-02 19:31:23
发布于：浙江
A789.Fence Planning--Silver
题目描述
农夫约翰的N 头奶牛，为了方便，编号 为1...N (2≤N≤10⁵)，它们具有复杂的社会结构，这种结构围绕着 “哞网络”——较小的奶牛群体它们在自己的群体内交流，但不与其他奶牛群体交流。每头奶牛在农场的地图上都位于一个不同的 (x,y)位置，我们知道 M 对奶牛 (1≤M<10⁵) 相互发出哞哞声。互相哞叫的奶牛属于同一个哞网络。为了更新他的农场，农民约翰想建造一个矩形围栏，其边缘与 x 轴和 y 轴平行。农民约翰想确保至少一个哞叫网络被围栏完全包围 (矩形边界上的奶牛被视为被包围)。请帮助农民约翰确定满足这一要求的围栏的最小可能周长。这个围栏可能具有零宽度零高度。)
输入格式
第一行输入包含 N 和 M。下面N 列每行包含一头奶牛的 x 和 y 坐标 (大小不超过 10 ⁸的非负整数)。接下来的 M 行每行包含两个整数 a 和 b, 指奶牛 a 和 b 之间的 哞网络连接。每头奶牛至少有一个 哞网络 连接，且输入中没有重复的连接。
输出格式
请打印出满足农夫约翰要求的最小围栏周长要求。
全部评论 3
农夫约翰的N头牛，方便起见编号为1…N（2≤N≤105），它们拥有以“哞哞网络”为核心的复杂社会结构——
即由若干较小的牛群组成，这些牛群仅在内部进行交流，而不与其他
牛群交流。
每头牛都位于农场二维地图上一个独特的 (x,y) 位置，
且我们知道有 M 对牛（1≤M<105）会互相“哞哞”叫。两头
互相“哞哞”叫的牛属于同一个“哞哞网络”。
为了改造农场，约翰农夫想建造一道矩形
围栏，其边与 x 轴和 y 轴平行。农夫约翰希望
确保至少有一个“哞”网络被围栏完全包围
（位于矩形边界上的奶牛也算作被包围）。请帮助
农夫约翰确定满足此要求的围栏
的最小周长。该围栏的宽度
或高度可以为零。
输入格式
输入的第一行包含 N 和 M。接下来的 N 行，每行包含
一头牛的 x 和 y 坐标（非负整数，大小不超过
10⁸）。接下来的 M 行，每行包含两个整数 a 和 b，描述牛 a 和牛 b 之间的
“哞”连接。每头牛至少有一个“哞”
连接，且输入中不存在重复的连接。通过DeepL.com（免费版）翻译
6天前 来自 北京
0
有帮助，赞一个