原试题 pdf 见#5034.「P154」马附件或直链。
你是能看到第三题的 friends 呢。 ——laekov
众所周知,小葱同学擅长计算,尤其擅长计算组合数,但这个题和组合数没什么关系。
座炮台,第 座炮台的坐标为 。现在有 两个运输中心,且他们中间有一条直接相连的边。
我们希望每座炮台的物资由某个运输中心提供,但是我们有 个限制条件,前 个限制条件是某两个炮台不能由同一个运输中心提供物资,而后 个条件是某两个炮台必须又同一个运输中心提供。
现在要求你最小化最远两个炮台之间的距离,问炮台之间距离最大值最小是多少。
注意这里两个点的距离都由曼哈顿距离定义。你可以认为这张图是某些炮台直接连到运输中心一,运输中心一连到运输中心二,运输中心二再连到其他炮台的一张图。