Menci

「APIO2013」TOLL - 搜索 + 最小生成树

幸福国度可以用 $N$ 个城镇（用 $1$ 到 $N$ 编号）构成的集合来描述，这些城镇最开始由 $M$ 条双向道路（用 $1$ 到 $M$ 编号）连接。城镇 $1$ 是中央城镇。保证一个人从城镇 $1$ 出发，经过这些道路，可以到达其他的任何一个城市。这些道路都是收费道路，道路 $i$ 的使用者必须向道路的主人支付 $c_i$ 分钱的费用。已知所有的这些 $c_i$ 是互不相等的。最近有 $K$ 条新道路建成，这些道路都属于亿万富豪 Mr. Greedy。

Mr. Greedy 可以决定每条新道路的费用（费用可以相同），并且他必须在明天宣布这些费用。

两周以后，幸福国度将举办一个盛况空前的嘉年华！大量的参与者将沿着这些道路游行并前往中央城镇。共计 $p_j$ 个参与者将从城镇 $j$ 出发前往中央城镇。这些人只会沿着一个选出的道路集合前行，并且这些选出的道路将在这件事的前一天公布。根据一个古老的习俗，这些道路将由幸福国度中最有钱的人选出，也就是 Mr. Greedy。同样根据这个习俗，Mr. Greedy 选出的这个道路集合必须使所有选出道路的费用之和最小，并且仍要保证任何人可以从城镇 $j$ 前往城镇 $1$ （因此，这些选出的道路来自将费用作为相应边边权的 “最小生成树”）。如果有多个这样的道路集合，Mr. Greedy 可以选其中的任何一个，只要满足费用和是最小的。

Mr. Greedy 很明确地知道，他从 $K$ 条新道路中获得的收入不只是与费用有关。一条道路的收入等于所有经过这条路的人的花费之和。更准确地讲，如果 $p$ 个人经过道路 $i$，道路 $i$ 产生的收入为乘积 $c_i \cdot p$。注意 Mr. Greedy 只能从新道路收取费用，因为原来的道路都不属于他。

Mr. Greedy 有一个阴谋。他计划通过操纵费用和道路的选择来最大化他的收入。他希望指定每条新道路的费用（将在明天公布），并且选择嘉年华用的道路（将在嘉年华的前一天公布），使得他在 $K$ 条新道路的收入最大。注意 Mr. Greedy 仍然需要遵循选出花费之和最小的道路集合的习俗。

你是一个记者，你想揭露他的计划。为了做成这件事，你必须先写一个程序来确定 Mr. Greedy 可以通过他的阴谋获取多少收入。

「JSOI2010」部落划分 - Kruskal

在二维平面上给若干个点，将这些点划分为若干个区域，定义两个区域的距离为这两个区域之间最近点对的距离。求将这些点划分为 $k$ 个区域，使得最近的两个区域的距离最大值。

「JSOI2008」最小生成树计数 - 搜索

求一个图的不同的最小生成树的数量，保证相同权值的边数量 $\leq 10$。

最小生成树 && 次小生成树

最近回顾了一下图论中的最小生成树算法，又学习了“次小生成树”的算法。