P5459. 骨干网管理域划分
场次：2026年9月16日 · 来源：CodeFun2000 P5459
题目描述
某省骨干网中部署了多台核心路由器。为提升运维效率，要把这些地理位置分散的设备在逻辑上划成 个管理域，并尽量让同一域内的设备彼此靠近，便于统一调度。
划分采用 Bi-K-means（二分 K-means）：一开始把全部设备看成一个簇 ，之后反复分裂当前最适合的簇，直到簇的个数等于 。
SSE（误差平方和）定义为
其中 是簇 的质心（各点坐标的算术平均）。将一个父簇裂成两个子簇时，SSE 下降量为
每一次从当前簇集合里选出一个簇，对其做 的 K-means 分裂，规则如下：
- 优先选择 最大的簇；若下降量相同，选择设备数更多的簇；若设备数也相同，选择生成时间更早的簇。初始簇 的生成时间最早；每次分裂得到的两个子簇按「先归入 最小初始质心一侧、后归入 最大初始质心一侧」依次生成，且都晚于其父簇。
- 对选中的簇做 2-means 时，必须取该簇内 坐标最小和 坐标最大的两个设备作为初始质心，禁止随机初始化。
- 若某设备到两个质心的欧氏距离相等，则划入 坐标较小的那个初始质心所在簇。
- 2-means 在下列任一条件成立时停止：两个新质心的最大偏移量（欧氏距离）小于 ；或所有设备的簇归属不再变化。
- 外层分裂进行到簇数等于 为止。第 次结果是尚未分裂的初始簇。
输入格式
第一行一个整数 ，表示期望得到的管理域（簇）个数，满足 。
第二行一个整数 ，表示核心路由器台数，满足 。
随后 行，每行两个整数 ，表示一台路由器的二维坐标（经度、纬度）。坐标均为整数，满足 ，且不同路由器的 坐标互不相同。
输出格式
输出 Bi-K-means 每一轮分裂后，当前各簇设备数的降序序列。初始簇 的设备数作为第 次的结果。共输出 行，第 行对应已经得到 个簇时的规模列表（同一行内以空格分隔）。
示例
示例 1
输入：
3
4
0 0
1 0
8 0
9 1
输出：
4
2 2
2 1 1
说明：
个点要划成 个管理域。
第 次：尚未分裂，只有 ，设备数为 。
第 次：对 做 2-means，初始质心取 最小的 与 最大的 。归属稳定后得到两个规模为 的簇： 与 ，降序为 。
第 次：左簇质心为 ，，裂成两个单点后 ；右簇质心为 ，，裂成两个单点后 。应分裂右簇，规模变为 ，降序为 。
示例 2
输入：
1
3
4 2
7 9
11 3
输出：
3
说明：
，不需要分裂，直接输出初始簇的设备数 。
解题思路
第一步：理解问题本质
题目要求实现的是二分 K-means（Bi-K-means），它和普通 K-means 的区别在于“簇是怎么来的”：
- 普通 K-means：一次性指定 个初始质心，反复“分配 + 更新质心”；
- 二分 K-means：从“全部点一个簇”开始，每次只把一个簇裂成两个，裂 次。
这样做的直接好处是结果确定：不需要随机初始化 个质心，也不会因为初始点选得不好而陷入很差的局部最优。代价是每一轮都要决定“裂哪个簇”。
“裂哪个簇”用 衡量。设父簇为 ，裂出的两个子簇为 ：
越小说明簇内越紧凑，所以 越大，说明这次分裂让整体误差下降得越多，这个簇就“越值得裂”。
题目还给了三级平局规则：
- 大的优先；
- 相同则设备数多的优先（大簇通常更值得细分）；
- 再相同则生成时间早的优先（先来的先裂，保证确定性）。
第二步：暴力解法——枚举所有二分方案
如果只按定义走，一个大小为 的簇裂成两个非空子集，共有 种划分方式。枚举全部划分、分别算 、取最小者，得到的就是“最优二分”：
# 枚举除最后一个点外每个点的归属，剩下的点固定在第 2 组，
# 这样每种划分恰好被数一次（避免 A/B 对称重复）
best_sse = float("inf")
for mask in range(1 << (m - 1)):
group_a, group_b = [], []
for i, p in enumerate(cluster):
# 最后一位为 1 的点固定归入 group_b，保证第 2 组非空
if i == m - 1 or (mask >> i) & 1:
group_b.append(p)
else:
group_a.append(p)
# mask 全为 1 时第 1 组为空，不是合法的二分，跳过
if not group_a:
continue
total = sse(group_a) + sse(group_b)
if total < best_sse:
best_sse = total
这个做法的正确性没有疑问，但代价是指数级：当 时， 根本无法计算。而且题目明确规定“必须取该簇内 x 坐标最小和 x 坐标最大的两个设备作为初始质心”，这其实是在指定用 2-means 迭代去近似这个最优二分，而不是真的枚举。
第三步：优化解法——用 2-means 近似最优二分
2-means（Lloyd 迭代）只需要两个初始质心，然后反复做两件事：
- 分配：每个点归到距离更近的质心；
- 更新：质心移动到本簇所有点的算术平均。
题面把细节全部钉死了：
| 细节 | 题目规定 |
|---|---|
| 初始质心 | 簇内 x 最小、x 最大的两个设备 |
| 距离相等 | 归入 x 较小的初始质心那一侧 |
| 停止条件 | 两个新质心的最大偏移量 或 归属不再变化（任一成立即停） |
| 质心 | 簇内点坐标的算术平均 |
| SSE | 到质心的欧氏距离平方和 |
“x 最小 / x 最大”这个初始化很关键：它保证两个初始质心一定不同，而且分出来的两簇初始都非空（最小的点离自己最近，最大的点也离自己最近），迭代不会一上来就出现空簇。
在距离相等时归入“x 较小的初始质心”，实现上就是把较小质心放在 a 侧，并用 <= 判断：
da = squared_distance(p, center_a)
db = squared_distance(p, center_b)
# 用 <= 而不是 <，保证“距离相等归入 x 较小的一侧”
label = 0 if da <= db else 1
迭代停止后，用两个子簇的 算 ，这就是这个簇的“分裂收益”。
第四步：最优解法——每轮重算候选，按三元组挑选
有了“给一个簇算分裂方案”的函数，外层流程就很直接：
while len(clusters) < target_clusters:
best = None
for pos, cluster in enumerate(clusters):
if len(cluster["members"]) < 2:
continue
gain, group_a, group_b = split_gain(points, cluster["members"])
# 三级优先级的元组写法：(下降量, 规模, -生成时间) 越大越优先。
# 真实代码用 GRAD_EPS 做浮点容差比较，这里用元组示意顺序。
key = (gain, len(cluster["members"]), -cluster["born"])
if best is None or key > best[0]:
best = (key, pos, group_a, group_b)
_, pos, group_a, group_b = best
# 先 x 较小一侧，后 x 较大一侧；两者的生成序号都大于父簇。
clusters[pos:pos + 1] = [
{"members": group_a, "born": clock},
{"members": group_b, "born": clock + 1},
]
clock += 2
# 输出当前所有簇的规模（降序）
几个必须注意的点：
- 必须真的把 2-means 跑完再算。 只跑一次分配、或者用“父簇 的一半”去估计，都会选错簇。题面要求的是“对当前簇集合里选出一个簇，对其做 的 K-means 分裂”，所以候选簇都要模拟完整分裂。
- 候选方案每轮重算，不做缓存。 簇的数量不超过 、点数不超过 ，重算的代价可以忽略；而缓存会引入“父簇已经变了、缓存却还是旧的”这类隐蔽错误。
- 生成时间用一个自增计数器表示。 初始簇 的序号是 ；每分裂一次，先给“x 较小一侧”的子簇分配
clock，再给“x 较大一侧”的分配clock+1，然后clock += 2。这样“谁更早”就是比较序号大小。 - 浮点比较要留容差。 两个本该相等的 可能因为累加顺序差出 ，直接用
>会让“设备数 / 生成时间”这两条平局规则失效。代码用GRAD_EPS = 1e-12判定并列。 - 输出是每一轮的“规模列表”，不是簇编号。 第 0 行只有初始簇的设备数 ；之后每行把当前各簇的设备数降序排列，空格分隔。
完整代码实现
import math
import sys
# 2-means 的质心偏移阈值，题面规定为 1e-6。
CENTROID_EPS = 1e-6
# SSE_Grad 的并列判定容差。浮点累加会有末位误差，直接用 == 比较会把
# “本来相等”的两个下降量判成不等，从而破坏“同分看设备数 / 生成时间”的规则。
GRAD_EPS = 1e-12
def squared_distance(p, q):
"""两点欧氏距离的平方。比较远近时不必开方，避免多余误差。"""
dx = p[0] - q[0]
dy = p[1] - q[1]
return dx * dx + dy * dy
def sse_of(points, indices, center):
"""簇内所有点到给定质心的距离平方和。"""
return sum(squared_distance(points[i], center) for i in indices)
def mean_point(points, indices):
"""簇内所有点坐标的算术平均，即质心。"""
sx = sum(points[i][0] for i in indices)
sy = sum(points[i][1] for i in indices)
n = len(indices)
return (sx / n, sy / n)
def two_means(points, indices):
"""
对已按 x 升序排列的下标列表做 2-means，返回两个子簇的下标列表。
返回值顺序固定：第 1 个子簇对应“x 最小的初始质心”，
第 2 个子簇对应“x 最大的初始质心”，这样调用方可以直接按题面规则
给它们分配生成时间。
"""
# 初始质心必须取簇内 x 最小、x 最大的两个设备。
centroid_a = points[indices[0]]
centroid_b = points[indices[-1]]
def assign(center_a, center_b):
"""按最近的质心分配；距离相等时归入 a（a 的初始质心 x 更小）。"""
labels = []
for idx in indices:
p = points[idx]
da = squared_distance(p, center_a)
db = squared_distance(p, center_b)
# 用 <= 保证“距离相等归入 x 较小的一侧”。
labels.append(0 if da <= db else 1)
return labels
labels = assign(centroid_a, centroid_b)
while True:
group_a = [idx for idx, lab in zip(indices, labels) if lab == 0]
group_b = [idx for idx, lab in zip(indices, labels) if lab == 1]
# 若某一侧为空，保留旧质心。正常数据下初始质心分别是首尾两个不同的点，
# 不会出现空簇，这里只是防御性处理。
new_a = mean_point(points, group_a) if group_a else centroid_a
new_b = mean_point(points, group_b) if group_b else centroid_b
# 两个新质心的最大欧氏偏移量。
shift = max(
math.sqrt(squared_distance(new_a, centroid_a)),
math.sqrt(squared_distance(new_b, centroid_b)),
)
new_labels = assign(new_a, new_b)
# 两个终止条件任一成立就停：质心基本不动，或归属不再变化。
if shift < CENTROID_EPS or new_labels == labels:
centroid_a, centroid_b = new_a, new_b
labels = new_labels
break
centroid_a, centroid_b = new_a, new_b
labels = new_labels
group_a = [idx for idx, lab in zip(indices, labels) if lab == 0]
group_b = [idx for idx, lab in zip(indices, labels) if lab == 1]
return group_a, group_b
def split_gain(points, indices):
"""
计算对一个簇做 2-means 分裂的 SSE_Grad。
SSE_Grad = SSE(父簇) - SSE(子簇1) - SSE(子簇2)。
"""
parent_center = mean_point(points, indices)
parent_sse = sse_of(points, indices, parent_center)
group_a, group_b = two_means(points, indices)
child_sse = 0.0
if group_a:
child_sse += sse_of(points, group_a, mean_point(points, group_a))
if group_b:
child_sse += sse_of(points, group_b, mean_point(points, group_b))
return parent_sse - child_sse, group_a, group_b
def solve():
"""读取点集，按题意反复分裂，输出每一轮的簇规模列表。"""
data = sys.stdin.buffer.read().split()
if len(data) < 2:
return
it = iter(data)
target_clusters = int(next(it))
total_points = int(next(it))
points = []
for _ in range(total_points):
x = int(next(it))
y = int(next(it))
points.append((x, y))
if total_points == 0 or target_clusters <= 0:
return
# 全局生成序号：C0 为 0，之后每分裂一次就分配两个更大的序号。
# 用序号代替真实时间，比较“谁更早”就是比较序号大小。
create_clock = 1
# 每个簇保存成员下标与生成时间。成员按 x 升序，two_means 依赖这个顺序
# 取首尾作为初始质心。
clusters = [{
"members": sorted(range(total_points), key=lambda i: points[i][0]),
"born": 0,
}]
# 第 0 次结果：尚未分裂，只有一个簇。
lines = [str(total_points)]
while len(clusters) < target_clusters:
best_index = -1
best_gain = -1.0
best_size = -1
best_born = 0
best_groups = None
for pos, cluster in enumerate(clusters):
members = cluster["members"]
# 只有一个点的簇无法再分裂（此时总点数不足，属于越界输入）。
if len(members) < 2:
continue
gain, group_a, group_b = split_gain(points, members)
# 依次比较：下降量更大 > 成员更多 > 生成时间更早。
if (gain > best_gain + GRAD_EPS
or (abs(gain - best_gain) <= GRAD_EPS
and len(members) > best_size)
or (abs(gain - best_gain) <= GRAD_EPS
and len(members) == best_size
and cluster["born"] < best_born)):
best_index = pos
best_gain = gain
best_size = len(members)
best_born = cluster["born"]
best_groups = (group_a, group_b)
# 所有簇都只剩一个点，无法继续分裂。属于 N > L 的越界输入，
# 直接按当前规模补齐剩余行，避免死循环。
if best_index == -1:
current = sorted((len(c["members"]) for c in clusters), reverse=True)
while len(lines) < target_clusters:
lines.append(" ".join(map(str, current)))
break
group_a, group_b = best_groups
# 先归入 x 最小初始质心一侧的子簇，再归入 x 最大一侧的子簇。
child_a = {"members": group_a, "born": create_clock}
child_b = {"members": group_b, "born": create_clock + 1}
create_clock += 2
clusters[best_index:best_index + 1] = [child_a, child_b]
current = sorted((len(c["members"]) for c in clusters), reverse=True)
lines.append(" ".join(map(str, current)))
print("\n".join(lines))
if __name__ == "__main__":
solve()
NumPy 版本
以下版本使用 NumPy。只有在评测环境允许第三方库时才能提交；CodeFun2000 的普通 Python 环境不一定安装 NumPy。
import sys
import numpy as np
# 2-means 的质心偏移阈值，题面规定为 1e-6
CENTROID_EPS = 1e-6
# SSE_Grad 的并列判定容差：浮点累加有末位误差，直接 == 会让
# “同分看设备数 / 生成时间”这两条平局规则失效
GRAD_EPS = 1e-12
def two_means(points, members):
"""对成员下标数组做 2-means，返回 (归入左侧质心的下标, 归入右侧质心的下标)。
约定：members 按 x 升序排列，所以首尾两个点就是“簇内 x 最小 / 最大”的设备，
正好是题面规定的初始质心；返回值顺序也固定成“先 x 较小、后 x 较大”，
调用方可以直接按这个顺序分配生成时间。
"""
sub = points[members] # (m, 2)，行按 x 升序
centroid_a = sub[0].copy() # x 最小的设备
centroid_b = sub[-1].copy() # x 最大的设备
def assign(center_a, center_b):
"""按最近的质心分配；距离相等时归入 a（a 的初始质心 x 更小）。"""
d2_a = ((sub - center_a) ** 2).sum(axis=1)
d2_b = ((sub - center_b) ** 2).sum(axis=1)
# d2_a <= d2_b 归 a（False），否则归 b（True）。
# 用 <= 而不是 <，保证“距离相等归入 x 较小的一侧”。
return d2_a > d2_b
labels = assign(centroid_a, centroid_b)
while True:
# 布尔掩码直接切出两簇；空簇时保留旧质心（正常数据不会出现）
group_a = sub[~labels]
group_b = sub[labels]
new_a = group_a.mean(axis=0) if group_a.size else centroid_a
new_b = group_b.mean(axis=0) if group_b.size else centroid_b
# 两个新质心的最大欧氏偏移量
shift = max(float(np.sqrt(((new_a - centroid_a) ** 2).sum())),
float(np.sqrt(((new_b - centroid_b) ** 2).sum())))
centroid_a, centroid_b = new_a, new_b
new_labels = assign(centroid_a, centroid_b)
# 两个终止条件任一成立就停：质心基本不动，或归属不再变化
if shift < CENTROID_EPS or np.array_equal(new_labels, labels):
labels = new_labels
break
labels = new_labels
return members[~labels], members[labels]
def split_gain(points, members):
"""算一次分裂的 SSE_Grad = SSE(父) - SSE(子1) - SSE(子2)。"""
parent = points[members]
parent_center = parent.mean(axis=0)
parent_sse = float(((parent - parent_center) ** 2).sum())
group_a, group_b = two_means(points, members)
child_sse = 0.0
for group in (group_a, group_b):
if group.size:
child = points[group]
child_center = child.mean(axis=0)
child_sse += float(((child - child_center) ** 2).sum())
return parent_sse - child_sse, group_a, group_b
def solve():
"""读入点集，按题意反复分裂，输出每一轮的簇规模列表。"""
data = sys.stdin.buffer.read().split()
if len(data) < 2:
return
target_clusters = int(data[0])
total_points = int(data[1])
coords = np.fromiter(map(int, data[2:2 + 2 * total_points]),
dtype=np.int64, count=2 * total_points)
points = coords.reshape(total_points, 2).astype(np.float64)
# 全局按 x 升序排一次。之后每个簇的成员都保持升序（分裂只是按掩码取子集），
# 首尾两个下标自然就是簇内 x 最小 / 最大的设备。
points = points[np.argsort(points[:, 0])]
if total_points == 0 or target_clusters <= 0:
return
# 全局生成序号：C0 为 0，之后每分裂一次分配两个更大的序号。
# 用序号代替真实时间，“谁更早”就是比序号大小。
create_clock = 1
clusters = [{"members": np.arange(total_points), "born": 0}]
# 第 0 次结果：尚未分裂，只有一个簇
lines = [str(total_points)]
while len(clusters) < target_clusters:
best_index = -1
best_gain = -1.0
best_size = -1
best_born = 0
best_groups = None
for pos, cluster in enumerate(clusters):
members = cluster["members"]
if members.size < 2: # 单点簇无法再分裂
continue
gain, group_a, group_b = split_gain(points, members)
size = int(members.size)
# 依次比较：下降量更大 > 成员更多 > 生成时间更早
if (gain > best_gain + GRAD_EPS
or (abs(gain - best_gain) <= GRAD_EPS
and size > best_size)
or (abs(gain - best_gain) <= GRAD_EPS
and size == best_size
and cluster["born"] < best_born)):
best_index = pos
best_gain = gain
best_size = size
best_born = cluster["born"]
best_groups = (group_a, group_b)
# 所有簇都只剩一个点（N > L 的越界输入）：按当前规模补齐剩余行，避免死循环
if best_index == -1:
current = sorted((int(c["members"].size) for c in clusters), reverse=True)
while len(lines) < target_clusters:
lines.append(" ".join(map(str, current)))
break
group_a, group_b = best_groups
# 先产生“归入 x 最小初始质心”的子簇，再产生“x 最大”的子簇
child_a = {"members": group_a, "born": create_clock}
child_b = {"members": group_b, "born": create_clock + 1}
create_clock += 2
clusters[best_index:best_index + 1] = [child_a, child_b]
current = sorted((int(c["members"].size) for c in clusters), reverse=True)
lines.append(" ".join(map(str, current)))
print("\n".join(lines))
if __name__ == "__main__":
solve()
示例推演
样例 1
输入 、，四个点是 。
第 0 次：尚未分裂，只有一个簇 ，设备数 ：
4
第 1 次分裂：对 跑 2-means。
初始质心取 x 最小的 与 x 最大的 ：
| 点 | 到 的距离平方 | 到 的距离平方 | 归属 |
|---|---|---|---|
| 左 | |||
| 左 | |||
| 右 | |||
| 右 |
新质心：左簇 ，右簇 。最大偏移量
用新质心重新分配：四个点仍然分别是“左、左、右、右”，归属没有变化，第二个停止条件成立，迭代结束。两个子簇规模都是 ，降序输出：
2 2
第 2 次分裂：分别算两个簇的 。
- 左簇 ：质心 ，
裂成两个单点后两个子簇的 都是 ，所以
- 右簇 ：质心 ，每个点到质心的距离平方都是 ，两个点共
裂成两个单点后同样为 ，所以
右簇的下降量更大，因此分裂右簇。右簇的初始质心是 与 ，一点一簇，规模变成 ：
2 1 1
此时簇数已经是 ，结束。完整输出：
4
2 2
2 1 1
样例 2
，一次分裂都不需要。初始簇的设备数为 ，直接输出：
3
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 枚举所有二分 | 指数级， 不可行 | ||
| 2-means 近似二分 | 单次分裂 | 为 Lloyd 迭代次数，实际只有几次 | |
| 每轮重算全部候选 | 本题采用； 为当前簇数 |
其中 、、。最坏情况下大约 少量迭代，计算量非常小。
易错点总结
1. 初始质心必须是 x 最小和 x 最大的设备
不能随机初始化，也不能取 y 最小/最大的点，更不能取几何上的“最左最右边界”。题面规定的是簇内某个设备，即取 points[min_x_index] 与 points[max_x_index]。
2. 距离相等要归入 x 较小的一侧
实现时把 x 较小的质心放在 a 侧，判断写成 da <= db。如果用 <，距离相等时会归到 b 侧，边界样例立刻出错。
3. 两个停止条件是“或”，不是“且”
质心最大偏移量小于 或 归属不再变化，任一成立就停。写成“且”会让迭代多做很多轮，虽然最终结果通常相同，但遇到来回震荡的归属时会死循环。
4. 计算 SSE_Grad 要真的跑完 2-means
只跑一次分配、只更新一次质心，或者直接用父簇 的一半来估计，都会得到错误的下降量，进而选错要分裂的簇。
5. 三级平局规则的顺序不能反
先比 （大），再比设备数（多），最后比生成时间（早）。设备数多不代表下降量大：一个分散的大簇可能 很小，而一个紧凑的小簇裂开后下降量反而更大。
6. 子簇的生成顺序与时间
每次分裂先产生“归入 x 最小初始质心”的子簇，再产生“归入 x 最大初始质心”的子簇，两者都晚于父簇。代码用 clock 与 clock+1 表示，且每次 clock += 2。
7. 输出的是每轮规模，且要降序
第 0 行是 ，之后每行是“已有 个簇时”的规模列表，同一行内必须降序。规模相同的簇不需要区分编号。
8. 浮点比较要留容差
是浮点数，两个理论上相等的值可能差 。直接 > 会让后两级平局规则永远不生效。用 量级的容差判定并列。
扩展思考
- 为什么用二分 K-means 而不是普通 K-means：普通 K-means 需要一次给出 个初始质心，不同初始化会得到不同结果；二分 K-means 的每一步都确定（初始质心固定、平局规则固定），适合机考这种要求唯一答案的场景。
- 如果 x 坐标允许重复：初始质心可能取到同一个点，两簇的初始划分就退化了。此时需要额外的平局规则（例如再按 y 比较，或按输入顺序取）。
- 其他分裂判据：除了 ，还可以选“半径最大”“点数最多”“最近邻距离最大”的簇来分裂。选哪种判据取决于希望得到“球形簇”“等大小簇”还是“密度簇”。
- 复杂度与 的关系：每轮都要对所有候选簇重算分裂，复杂度与 近似平方相关。若 很大，可以把每个簇的分裂结果缓存起来，只重算刚刚被裂开的两个子簇。
- K-means 的固有局限：它只能找到“凸的、大小相近”的簇，对环形、月牙形分布无能为力；这类数据需要 DBSCAN、谱聚类等方法。