P2610 [ZJOI2012]旅游

    • 200通过
    • 483提交
  • 题目提供者 TMXi
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 广度优先搜索,BFS 树的直径 各省省选 2012 浙江 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

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

    输入输出格式

    输入格式:

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

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

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    6
    1 2 4
    2 3 4
    1 4 5
    1 5 6
    输出样例#1: 复制
    4

    说明

    对于20%的数据, n<=2000

    对于100%的数据, 4<=n<=200000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。