AC. 梦想

frank_c1

[BZOJ 2657] 旅游

发布于2016年02月27日 | 暂无评论 | 505阅读 |

题目描述

到了难得的暑假,为了庆祝小白在数学考试中取得的优异成绩,小蓝决定带小白出去旅游~~

经过一番抉择,两人决定将T国作为他们的目的地。T国的国土可以用一个凸N边形来表示,N个顶点表示N个入境/出境口。T国包含N-2个城市,每个城市都是顶点均为N边形顶点的三角形(换而言之,城市组成了关于T国的一个三角剖分)。两人的旅游路线可以看做是连接N个顶点中不相邻两点的线段。

为了能够买到最好的纪念品,小白希望旅游路线上经过的城市尽量多。作为小蓝的好友,你能帮帮小蓝吗?

输入格式

每个输入文件中仅包含一个测试数据。

第一行包含两个由空格隔开的正整数N,N的含义如题目所述。

接下来有N-2行,每行包含三个整数 p,q,r,表示该城市三角形的三个顶点的编号(T国的N个顶点按顺时间方向从1至n编号)。

输出格式

输出文件共包含1行,表示最多经过的城市数目。(一个城市被当做经过当且仅当其与线路有至少两个公共点)

题目解析

一开始还以为是计算几何,后来觉得这种不定形状的还是应该用图论解决。

解决此题,需要挖掘三角剖分的性质,一个三角剖分可以把一个凸n边形划分成n-2个区域,在凸n边形内部应有n-3条边。如果我们把每个城市当做一个点,相邻的区域连上一条边,毫无疑问,这样构成的图是连通的。所以这是一棵树。

转化成一棵树后问题便清晰了,题目所求即是树的直径。