Tag: 变形

POJ-2253 解题报告

题意简述 湖中有N（2<=N<=200）块石头，标号从1到N。青蛙1在石头1上，青蛙2在石头2上。给定所有的石头坐标。青蛙1试图从石头1到石头2来找青蛙2，它可以经由任意石头组成的路径。在所有可能路径中找出一条路径，使其中最长的一步的长度小于其他路径中最长的一步的长度。 本题可以化简为，点1与点2间存在若干条路径，每条路径中都存在最长的一条边。找出一条路径使得该路径最长边的长度小于其他任意路径最长边。