CF471E MUH and Lots and Lots of Segments
题目描述
圣彼得堡动物园的北极熊 Menshykov 和 Uslada，以及基辅动物园的大象 Horace 决定一起画画。当他们尝试创作第一幅杰作时，在纸上画了一份草稿。草稿由 $n$ 条线段组成，每条线段要么水平、要么垂直。现在，朋友们想要通过删除某些线段或线段的一部分，简化草稿，使得最终的杰作满足以下三个条件：
1. Horace 希望能够“一笔画完”整幅画：将画笔放到纸上，不抬起画笔直到画作完成。画笔可以多次经过同一个地方。因此，所有剩下的线段必须构成一个连通形状。
2. Menshykov 希望最终的形状足够简单，他定义简单形状为：形状中不包含任何环。
3. 所有草稿中的线段的起点和终点坐标都是整数。Uslada 不喜欢实数坐标，她希望在做所有修改后，这一条件仍然成立。
因为草稿在其他方面已经很美了，朋友们决定仅删除那些使得剩下线段长度总和尽可能大的部分。你的任务就是计算，经过这些操作后，剩余线段的长度之和的最大值。
输入格式
输入描述同上。
输出格式
输出一行一个整数，表示保留下来的线段的最大总长度。
说明/提示
对于样例给出的两种可能的形状如下：
在第一个样例中，你需要删除任意一段线段，因为两段线段在一起并不连通。
在第二个样例中，初始的线段构成了一个环，有四种方式可以打破这个环：删除第一、第二或者第四条线段中的任意一条，或者将第三条线段中间的一部分删除。最后一种方式如图所示。
由 ChatGPT 5 翻译