洛谷4049 [JSOI2007]合金
Luogu 分析 将每种金属看做一个点 $(a_i, b_i)$，那么两点能配出的所有合金一定在两点构成的线段上。 问题转为给出 $m$ 个点，求一个以这 $m$ 个点为顶点的边数最少的多边形包含 $n$ 个关键点。 如果 $n$ 个点都在 $(x,y)$ 左侧，连一条从 $x$ 到 $y$ 的边权为 $1$ 的边，这样子满足条件的多边形就变成了图上的一个圈。 我们需要求最小圈， Floy...
Luogu 分析 将每种金属看做一个点 $(a_i, b_i)$，那么两点能配出的所有合金一定在两点构成的线段上。 问题转为给出 $m$ 个点，求一个以这 $m$ 个点为顶点的边数最少的多边形包含 $n$ 个关键点。 如果 $n$ 个点都在 $(x,y)$ 左侧，连一条从 $x$ 到 $y$ 的边权为 $1$ 的边，这样子满足条件的多边形就变成了图上的一个圈。 我们需要求最小圈， Floy...