解题思路

本题要求实现二分 K-means (Bi-Kmeans) 算法来解决网络子网分割问题。该算法是对传统 K-means 算法的优化，能够有效避免陷入局部最优解。

算法的核心思想是采用自顶向下的分裂策略，每次选择一个簇进行二分，直到达到目标簇数量。具体流程如下：

首先，将所有网络站点作为一个整体，使用标准 K-means 算法（K=2）将其分割成两个子网。在进行 K-means 聚类时，选取子网中 x 坐标最小和最大的两个站点作为初始簇心，然后迭代更新簇心（使用簇内所有站点的平均坐标），直到簇心变化小于阈值或达到最大迭代次数。

接下来，算法进入主循环，每次迭代都需要从现有的所有簇中选择一个进行进一步划分。选择的标准是基于 SSE（误差平方和）最小化原则：计算每个簇被划分前后的 SSE 差值，选择能够最大程度降低全局 SSE 的簇进行划分。SSE 的计算方式是以簇的平均坐标为簇心，计算簇内所有站点到簇心的欧氏距离平方和。

每次划分后，都需要输出当前所有簇的站点数量，并按降序排列。重复这个过程，直到簇的数量达到预期值 N。

需要注意的边界情况包括：只有一个站点的簇无法继续划分；簇的分配需要基于站点到簇心的最小欧氏距离；迭代过程中需要处理空簇的情况。

代码实现

Python

import numpy as np

def calculate_sse(points):
    # 计算簇的SSE（误差平方和）
    if len(points) == 0:
        return 0
    center = np.mean(points, axis=0)
    return np.sum((points - center) ** 2)

def kmeans_split(points):
    # 使用K-means算法将点集分成两个簇
    if len(points) <= 1:
        return [points]
    
    # 选择x坐标最小和最大的点作为初始簇心
    min_idx = np.argmin(points[:, 0])
    max_idx = np.argmax(points[:, 0])
    centers = np.array([points[min_idx], points[max_idx]])
    
    # 迭代更新簇心
    for _ in range(1000):
        # 计算每个点到两个簇心的距离
        distances = np.sum((points[:, np.newaxis] - centers) ** 2, axis=2)
        labels = np.argmin(distances, axis=1)
        
        # 更新簇心
        new_centers = np.array([
            np.mean(points[labels == 0], axis=0) if np.any(labels == 0) else centers[0],
            np.mean(points[labels == 1], axis=0) if np.any(labels == 1) else centers[1]
        ])
        
        # 检查是否收敛
        if np.sum((centers - new_centers) ** 2) < 1e-12:
            break
        
        centers = new_centers
    
    # 最终分配
    distances = np.sum((points[:, np.newaxis] - centers) ** 2, axis=2)
    labels = np.argmin(distances, axis=1)
    
    return [points[labels == 0], points[labels == 1]]

def bi_kmeans(points, n):
    # 二分K-means算法主函数
    clusters = [points]
    results = []
    
    # 第一次划分
    clusters = kmeans_split(clusters[0])
    sizes = sorted([len(c) for c in clusters], reverse=True)
    results.append(sizes)
    
    # 继续划分直到达到目标簇数量
    while len(clusters) < n:
        max_sse_reduction = -1
        best_idx = -1
        
        # 选择划分后SSE减少最多的簇
        for i in range(len(clusters)):
            if len(clusters[i]) <= 1:
                continue
            
            current_sse = calculate_sse(clusters[i])
            new_clusters = kmeans_split(clusters[i])
            new_sse = sum(calculate_sse(c) for c in new_clusters)
            sse_reduction = current_sse - new_sse
            
            if sse_reduction > max_sse_reduction:
                max_sse_reduction = sse_reduction
                best_idx = i
        
        # 划分选中的簇
        new_clusters = kmeans_split(clusters[best_idx])
        clusters = clusters[:best_idx] + new_clusters + clusters[best_idx + 1:]
        
        sizes = sorted([len(c) for c in clusters], reverse=True)
        results.append(sizes)
    
    return results

# 主函数
n = int(input())
m = int(input())
points = np.array([list(map(int, input().split())) for _ in range(m)], dtype=float)

results = bi_kmeans(points, n)
for result in results:
    print(' '.join(map(str, result)))

Java

import java.util.*;

public class Main {
    static class Point {
        double x, y;
        
        Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
    }
    
    // 计算两点之间的欧氏距离平方
    static double calculateDistanceSquared(Point p1, Point p2) {
        return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
    }
    
    // 计算点集的平均坐标（簇心）
    static Point calculateCenter(List<Point> points) {
        double xSum = 0, ySum = 0;
        for (Point p : points) {
            xSum += p.x;
            ySum += p.y;
        }
        return new Point(xSum / points.size(), ySum / points.size());
    }
    
    // 计算簇的SSE（误差平方和）
    static double calculateSSE(List<Point> points) {
        if (points.isEmpty()) return 0;
        Point center = calculateCenter(points);
        double sse = 0;
        for (Point p : points) {
            sse += calculateDistanceSquared(p, center);
        }
        return sse;
    }
    
    // 使用K-means算法将点集分成两个簇
    static List<List<Point>> kmeansSplit(List<Point> points) {
        if (points.size() <= 1) {
            List<List<Point>> result = new ArrayList<>();
            result.add(new ArrayList<>(points));
            return result;
        }
        
        // 选择x坐标最小和最大的点作为初始簇心
        Point minXPoint = points.get(0);
        Point maxXPoint = points.get(0);
        for (Point p : points) {
            if (p.x < minXPoint.x) minXPoint = p;
            if (p.x > maxXPoint.x) maxXPoint = p;
        }
        
        Point[] centers = {new Point(minXPoint.x, minXPoint.y), 
                          new Point(maxXPoint.x, maxXPoint.y)};
        
        // 迭代更新簇心
        for (int iter = 0; iter < 1000; iter++) {
            // 将每个点分配到最近的簇心
            List<List<Point>> clusters = new ArrayList<>();
            clusters.add(new ArrayList<>());
            clusters.add(new ArrayList<>());
            
            for (Point p : points) {
                double dist0 = calculateDistanceSquared(p, centers[0]);
                double dist1 = calculateDistanceSquared(p, centers[1]);
                if (dist0 <= dist1) {
                    clusters.get(0).add(p);
                } else {
                    clusters.get(1).add(p);
                }
            }
            
            // 更新簇心
            Point[] newCenters = new Point[2];
            for (int i = 0; i < 2; i++) {
                if (!clusters.get(i).isEmpty()) {
                    newCenters[i] = calculateCenter(clusters.get(i));
                } else {
                    newCenters[i] = centers[i];
                }
            }
            
            // 检查是否收敛
            if (calculateDistanceSquared(centers[0], newCenters[0]) < 1e-12 &&
                calculateDistanceSquared(centers[1], newCenters[1]) < 1e-12) {
                break;
            }
            
            centers = newCenters;
        }
        
        // 最终分配
        List<List<Point>> clusters = new ArrayList<>();
        clusters.add(new ArrayList<>());
        clusters.add(new ArrayList<>());
        for (Point p : points) {
            double dist0 = calculateDistanceSquared(p, centers[0]);
            double dist1 = calculateDistanceSquared(p, centers[1]);
            if (dist0 <= dist1) {
                clusters.get(0).add(p);
            } else {
                clusters.get(1).add(p);
            }
        }
        
        return clusters;
    }
    
    // 二分K-means算法主函数
    static List<List<Integer>> biKmeans(List<Point> points, int n) {
        List<List<Point>> clusters = new ArrayList<>();
        clusters.add(new ArrayList<>(points));
        List<List<Integer>> results = new ArrayList<>();
        
        // 第一次划分
        List<List<Point>> newClusters = kmeansSplit(clusters.get(0));
        clusters = newClusters;
        
        List<Integer> sizes = new ArrayList<>();
        for (List<Point> cluster : clusters) {
            sizes.add(cluster.size());
        }
        Collections.sort(sizes, Collections.reverseOrder());
        results.add(sizes);
        
        // 继续划分直到达到目标簇数量
        while (clusters.size() < n) {
            double maxSSEReduction = -1;
            int bestIdx = -1;
            
            // 选择划分后SSE减少最多的簇
            for (int i = 0; i < clusters.size(); i++) {
                if (clusters.get(i).size() <= 1) continue;
                
                double currentSSE = calculateSSE(clusters.get(i));
                List<List<Point>> splitClusters = kmeansSplit(clusters.get(i));
                double newSSE = 0;
                for (List<Point> c : splitClusters) {
                    newSSE += calculateSSE(c);
                }
                double sseReduction = currentSSE - newSSE;
                
                if (sseReduction > maxSSEReduction) {
                    maxSSEReduction = sseReduction;
                    bestIdx = i;
                }
            }
            
            // 划分选中的簇
            List<List<Point>> splitClusters = kmeansSplit(clusters.get(bestIdx));
            List<List<Point>> newClustersList = new ArrayList<>();
            for (int i = 0; i < clusters.size(); i++) {
                if (i == bestIdx) {
                    newClustersList.addAll(splitClusters);
                } else {
                    newClustersList.add(clusters.get(i));
                }
            }
            clusters = newClustersList;
            
            sizes = new ArrayList<>();
            for (List<Point> cluster : clusters) {
                sizes.add(cluster.size());
            }
            Collections.sort(sizes, Collections.reverseOrder());
            results.add(sizes);
        }
        
        return results;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        List<Point> points = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            double x = sc.nextDouble();
            double y = sc.nextDouble();
            points.add(new Point(x, y));
        }
        
        List<List<Integer>> results = biKmeans(points, n);
        for (List<Integer> result : results) {
            for (int i = 0; i < result.size(); i++) {
                if (i > 0) System.out.print(" ");
                System.out.print(result.get(i));
            }
            System.out.println();
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
};

// 计算两点之间的欧氏距离平方
double calculateDistanceSquared(const Point& p1, const Point& p2) {
    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}

// 计算点集的平均坐标（簇心）
Point calculateCenter(const vector<Point>& points) {
    double xSum = 0, ySum = 0;
    for (const Point& p : points) {
        xSum += p.x;
        ySum += p.y;
    }
    return Point(xSum / points.size(), ySum / points.size());
}

// 计算簇的SSE（误差平方和）
double calculateSSE(const vector<Point>& points) {
    if (points.empty()) return 0;
    Point center = calculateCenter(points);
    double sse = 0;
    for (const Point& p : points) {
        sse += calculateDistanceSquared(p, center);
    }
    return sse;
}

// 使用K-means算法将点集分成两个簇
vector<vector<Point>> kmeansSplit(const vector<Point>& points) {
    if (points.size() <= 1) {
        return {points};
    }
    
    // 选择x坐标最小和最大的点作为初始簇心
    Point minXPoint = points[0];
    Point maxXPoint = points[0];
    for (const Point& p : points) {
        if (p.x < minXPoint.x) minXPoint = p;
        if (p.x > maxXPoint.x) maxXPoint = p;
    }
    
    vector<Point> centers = {minXPoint, maxXPoint};
    
    // 迭代更新簇心
    for (int iter = 0; iter < 1000; iter++) {
        // 将每个点分配到最近的簇心
        vector<vector<Point>> clusters(2);
        for (const Point& p : points) {
            double dist0 = calculateDistanceSquared(p, centers[0]);
            double dist1 = calculateDistanceSquared(p, centers[1]);
            if (dist0 <= dist1) {
                clusters[0].push_back(p);
            } else {
                clusters[1].push_back(p);
            }
        }
        
        // 更新簇心
        vector<Point> newCenters(2);
        for (int i = 0; i < 2; i++) {
            if (!clusters[i].empty()) {
                newCenters[i] = calculateCenter(clusters[i]);
            } else {
                newCenters[i] = centers[i];
            }
        }
        
        // 检查是否收敛
        if (calculateDistanceSquared(centers[0], newCenters[0]) < 1e-12 &&
            calculateDistanceSquared(centers[1], newCenters[1]) < 1e-12) {
            break;
        }
        
        centers = newCenters;
    }
    
    // 最终分配
    vector<vector<Point>> clusters(2);
    for (const Point& p : points) {
        double dist0 = calculateDistanceSquared(p, centers[0]);
        double dist1 = calculateDistanceSquared(p, centers[1]);
        if (dist0 <= dist1) {
            clusters[0].push_back(p);
        } else {
            clusters[1].push_back(p);
        }
    }
    
    return clusters;
}

// 二分K-means算法主函数
vector<vector<int>> biKmeans(const vector<Point>& points, int n) {
    vector<vector<Point>> clusters = {points};
    vector<vector<int>> results;
    
    // 第一次划分
    vector<vector<Point>> newClusters = kmeansSplit(clusters[0]);
    clusters = newClusters;
    
    vector<int> sizes;
    for (const auto& cluster : clusters) {
        sizes.push_back(cluster.size());
    }
    sort(sizes.begin(), sizes.end(), greater<int>());
    results.push_back(sizes);
    
    // 继续划分直到达到目标簇数量
    while ((int)clusters.size() < n) {
        double maxSSEReduction = -1;
        int bestIdx = -1;
        
        // 选择划分后SSE减少最多的簇
        for (int i = 0; i < (int)clusters.size(); i++) {
            if (clusters[i].size() <= 1) continue;
            
            double currentSSE = calculateSSE(clusters[i]);
            vector<vector<Point>> splitClusters = kmeansSplit(clusters[i]);
            double newSSE = 0;
            for (const auto& c : splitClusters) {
                newSSE += calculateSSE(c);
            }
            double sseReduction = currentSSE - newSSE;
            
            if (sseReduction > maxSSEReduction) {
                maxSSEReduction = sseReduction;
                bestIdx = i;
            }
        }
        
        // 划分选中的簇
        vector<vector<Point>> splitClusters = kmeansSplit(clusters[bestIdx]);
        vector<vector<Point>> newClustersList;
        for (int i = 0; i < (int)clusters.size(); i++) {
            if (i == bestIdx) {
                for (const auto& c : splitClusters) {
                    newClustersList.push_back(c);
                }
            } else {
                newClustersList.push_back(clusters[i]);
            }
        }
        clusters = newClustersList;
        
        sizes.clear();
        for (const auto& cluster : clusters) {
            sizes.push_back(cluster.size());
        }
        sort(sizes.begin(), sizes.end(), greater<int>());
        results.push_back(sizes);
    }
    
    return results;
}

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<Point> points(m);
    for (int i = 0; i < m; i++) {
        cin >> points[i].x >> points[i].y;
    }
    
    vector<vector<int>> results = biKmeans(points, n);
    for (const auto& result : results) {
        for (int i = 0; i < (int)result.size(); i++) {
            if (i > 0) cout << " ";
            cout << result[i];
        }
        cout << endl;
    }
    
    return 0;
}

题目内容

背景：在网络规划中，经常涉及子网分割问题，子网分割的目的是将距离相近的网络站点划分为一个子网，从而便于管理。

问题：聚类算法可以很好的解决子网分割问题，但是，聚类问题容易陷入局部最优。因此，本题期望采用优化版的聚类算法二分 $Kmeans$ 算法（$Bi-Kmeans$）进行子网分割。

方案概述：$Bi-Kmeans$ 算法首先将全网按照常规的 $Kmeans$ 算法聚类成两个子网（也就是 $K=2$，两簇），然后，$Bi-Kmeans$ 算法会基于 $SSE$（$Sum$ $of$ $Squared$ $Error$）最小化原理，每次迭代只选择一个子网进一步划分，选择子网的原则是对该子网的进一步划分能够最大程度的降低全局 $SSE$，划分方法依旧是常规的 $Kmeans$ 算法（$K=2$），直到子网个数达到预期数量时，停止 $Bi-Kmeans$ 算法的迭代（算法实现细节参见下述备注 $1/2/3$）。

备注 $1$-初始值选取：在进行常规 $Kmeans$ 聚类（$K=2$）二分子网时，选取子网中 $x$ 坐标最小和最大的两个站点作为初始簇心进行划分（网络站点拥有不同的 $x$ 坐标，本题中 $x$ 坐标的最小值和最大值唯一）。

备注 $2$-算法迭代：在进行常规 $Kmeans$ 聚类（$K=2$）二分子网时，以簇中全部站点的平均坐标作为更新簇心；如果相邻的两次迭代聚类结果相同（各簇心迭代前后之间的距离小于 $1e^{-6}$ 则视为结果相同），则停止迭代，或者当迭代次数达到 $1000$ 次时停止迭代。

备注 $3-SSE$ 计算：以子网中全部站点的平均坐标为簇心，$SSE$ 的计算方式是簇内所有站点到簇心距离的平方之和。

输入描述

输入包括三部分信息：

1）第一行数据表示期望分割的子网数量，用 $N$ 表示，也就是聚类结果中簇的数量；$N$ 是整数，范围 $1<=N<=100$ 。

2）第二行数据表示全网站点总数，用 $M$ 表示；$M$ 是整数，范围 $1<=M<=1000$ 。

3）从第三行开始的数据表示网络站点坐标，每一行代表一个站点的二维坐标，用空格分隔 $x$ 轴坐标和 $y$ 轴坐标； $x$ 轴坐标和 $y$ 轴坐标均为整数，$0<=x$ 轴坐标 $<=1000$，$0<=y$ 轴坐标 $< =1000$ 。

输出描述

输出用二维数组记录划分的最终结果和划分过程，其中，第 $k$ 行记录第 $k$ 次划分后的结果，结果包含第 $k$ 次划分后每个子网的站点数量，用空格分隔，并按照降序排列。

样例1

输入

3 
3 
0 0 
2 2 
5 5 

输出

2 1 
1 1 1

说明

输入表示我们期望将坐标分别为 $(0,0)、(2,2)、(5,5)$ 的 $3$ 个网络站点划分为 $3$ 个子网。 按照题目要求，需要经过两次划分，第一次划分的结果为：

簇 $1$ $1=[(0,0),(2,2)]$

簇 $1$ $2=[(5,5)]$

因此，期望输出的第一行是 $2$ $1$，其中，$2$ 表示划分结果簇 $1$ $1$ 有 $2$ 个站点，$1$ 表示划分结果簇 $1$ $2$ 有 $1$ 个站点，降序排列。

第二次划分的结果为：

簇 $2$ $1=[(0,0)]$

簇 $2$ $2=[(2,2)]$

簇 $2$ $3=[(5,5)]$

因此，期望输出的第二行是 $1$ $1$ $1$，其中，第一个 $1$ 表示划分结果簇 $2$ $1$ 有 $1$ 个站点，第二个 $1$ 表示划分结果簇 $2$ $2$ 有 $1$ 个站点，第三个 $1$ 表示划分结果簇 $2$ $3$ 有 $1$ 个站点，降序排列。

样例2

输入

2 
3 
0 0 
2 2 
5 5

输出

2 1

说明

输入表示我们期望将坐标分别为 $(0,0)、(2,2)、(5,5)$ 的 $3$ 个网络站点划分为 $2$ 个子网。

按照题目要求，需要经过一次划分，划分的结果为：

簇 $1=[(0,0),(2,2)]$

簇 $2=[(5,5)]$

因此，期望输出是 $2$ $1$，其中，$2$ 表示划分结果簇 $1$ 有 $2$ 个站点，$1$ 表示划分结果簇 $2$ 有 $1$ 个站点，降序排列。