吃饭路上也要锻炼 题解

这里是分五层做法↓↓↓!!!

从两头开始往中间“夹”：农场1是第一层，农场2是第五层；与农场1有一条边相连的农场们是第二层，与农场2有一条边相连的农场们是第四层。剩下的都“堆”成第三层。

考虑答案的合法性和最大化两点。

如果一条直线从第一层穿到第五层只能出现四条路径，不合法。如果像这样一层一层紧接着连下来都不合法，且保证设计出的最短路已存在5，那么跨层连是必不合法的。

什么时候会出现上述第一种“穿串”的情况？第三层存在一点与二四层都有连边。这种情况在已设计好的路线中是不可能存在的，所以我们在建新路时避免即可。

同层的点可连线以优化答案。

第三层与第二层有连边的点去和第二层的所有点连一遍，第三层与第四层有连边的点去和第四层的所有点连一遍。没有如上连边的点连第二层所有点或第四层所有点均可，不过肯定是选点更多的一侧来连。

记得去重！！！