An unavoidable detour for home
题意
有n座城市，城市间可能有无向边连接。有以下特点：
- 两座城市间最多一条边，不会有边连接自己。
-
定义第一座城市为首都，每座城市到首都的路径经过的边数为距离，那么每座城市必有且只有一条到首都的最短路径，下称第i座城市到首都的最短距离为
image.png
由2可知，每座城市必定连接编号比自己小的城市，所以有且，否则i的最短距就要大于i-1的了，如上图中城市7只能在4,、5、 6中选一个连接。
如果我们逐个城市逐个城市地加入路网，每个城市必须和前面的城市连一条路，剩下的路可以继续和前面的连接(注意最短路径唯一)，也可以留着给后来的城市连接，那么任意时刻，剩余度数大于0的城市的最短距最多两种，且它们的差为1，且它们是最短距最大的，而题目限定了每个城市的度数为2或3，所以剩余度数有1,2，也就是说，剩余可连的城市最多只有四种。
到了这一步，结合n的大小，看起来是不是很像dp？dp的转移公式也很明显了，如果担心遍历50*50*50*50太慢，可以剪枝。
网友评论