二分 K-means子网分割

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
struct group {
    double SSE;
    vector<int>members;//保证升序
    group(double SSE, const vector<int>& members): SSE(SSE), members(members) {}
    bool operator<(const group& other)const {
        if (members.size() == other.members.size()) {
            return SSE < other.SSE;
        }
        return members.size() < other.members.size();
    }
};
vector<pair<int, int>>a;
bool cmp(const int p1, const int p2) {
    if (a[p1].first == a[p2].first) {
        return a[p1].second < a[p2].second;
    }
    return a[p1].first < a[p2].first;
}
long long dist2(int i, int j) {
    return (a[i].first - a[j].first) * (a[i].first - a[j].first) +
           (a[i].second - a[j].second) * (a[i].second - a[j].second);
}
double getSSE(vector<int>& mem) {
    double x = 0;
    double y = 0;
    for (int i : mem) {
        x += a[i].first;
        y += a[i].second;
    }
    x /= mem.size();
    y /= mem.size();
    double SSE = 0;
    for (int i : mem) {
        SSE += (a[i].first - x) * (a[i].first - x) + (a[i].second - y) *
               (a[i].second - y);
    }
    return SSE;
}
int main() {
    int n, m;
    cin >> n >> m;
    a.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i].first >> a[i].second;
    }
    //交换顺序不影响结果
    sort(a.begin(), a.end());
    vector<int>tmp;
    for (int i = 0; i < m; i++) {
        tmp.push_back(i);
    }
    priority_queue<group>pq;
    map<int, int> flag;
    flag[m]++;
    pq.push(group(0, tmp));
    vector<vector<int>>ans;
    while (pq.size() < n) {
        group now = pq.top();
        pq.pop();
        int a1 = now.members[0];
        int a2 = now.members[now.members.size() - 1];
        flag[now.members.size()]--;
        if (flag[now.members.size()] == 0) {
            flag.erase(now.members.size());
        }
        vector<int>mem1, mem2;
        mem1.push_back(a1);
        for (int i = 1; i < now.members.size() - 1; i++) {
            long long d1 = dist2(i, a1);
            long long d2 = dist2(i, a2);
            if (d1 < d2) {
                mem1.push_back(i);
            } else {
                mem2.push_back(i);
            }
        }
        mem2.push_back(a2);
        pq.push(group(getSSE(mem1), mem1));
        pq.push(group(getSSE(mem2), mem2));
        flag[mem1.size()]++;
        flag[mem2.size()]++;
        vector<int>tmp;//从小到大
        for (auto& pair : flag) {
            for (int i = 0; i < pair.second; i++)
                tmp.push_back(pair.first);
        }
        ans.push_back(tmp);
    }
    for (int i = 0; i < ans.size(); i++) {
        //倒序输出
        for (int j = ans[i].size() - 1; j >= 0; j--) {
            cout << ans[i][j] << " ";
        }
        cout << "\n";
    }
}

#include <bits/stdc++.h>
using namespace std;

const int MAXP = 100010; // 最大点数
const int MAXC = 50;     // 最大簇数（N ≤ 50假设）

double px[MAXP], py[MAXP]; // 点坐标
int cluster_members[MAXC][MAXP]; // 每簇的成员点下标
int cluster_size[MAXC]; // 每簇成员数
double center_x[MAXC], center_y[MAXC], sse[MAXC]; // 簇心 & SSE

int N, M; // 簇目标数量 & 点数量

void compute_center_sse(int cid) {
    double sumx = 0, sumy = 0;
    for (int i = 0; i < cluster_size[cid]; ++i) {
        int pid = cluster_members[cid][i];
        sumx += px[pid];
        sumy += py[pid];
    }
    center_x[cid] = sumx / cluster_size[cid];
    center_y[cid] = sumy / cluster_size[cid];

    double total_sse = 0;
    for (int i = 0; i < cluster_size[cid]; ++i) {
        int pid = cluster_members[cid][i];
        double dx = px[pid] - center_x[cid];
        double dy = py[pid] - center_y[cid];
        total_sse += dx*dx + dy*dy;
    }
    sse[cid] = total_sse;
}

// 二分 K-means 分裂簇 cid -> 新簇 cid1, cid2
bool split_cluster(int cid, int cid1, int cid2) {
    if (cluster_size[cid] <= 1) return false;

    // 找 x最小和最大点
    double minx = px[cluster_members[cid][0]], maxx = minx;
    int min_id = cluster_members[cid][0], max_id = min_id;
    for (int i = 1; i < cluster_size[cid]; ++i) {
        int pid = cluster_members[cid][i];
        if (px[pid] < minx) { minx = px[pid]; min_id = pid; }
        if (px[pid] > maxx) { maxx = px[pid]; max_id = pid; }
    }

    double cx1 = px[min_id], cy1 = py[min_id];
    double cx2 = px[max_id], cy2 = py[max_id];

    for (int it = 0; it < 1000; ++it) {
        cluster_size[cid1] = 0;
        cluster_size[cid2] = 0;

        // 分配
        for (int i = 0; i < cluster_size[cid]; ++i) {
            int pid = cluster_members[cid][i];
            double d1 = (px[pid]-cx1)*(px[pid]-cx1)+(py[pid]-cy1)*(py[pid]-cy1);
            double d2 = (px[pid]-cx2)*(px[pid]-cx2)+(py[pid]-cy2)*(py[pid]-cy2);
            if (d1 <= d2) cluster_members[cid1][cluster_size[cid1]++] = pid;
            else cluster_members[cid2][cluster_size[cid2]++] = pid;
        }

        if (cluster_size[cid1] == 0 || cluster_size[cid2] == 0) return false;

        // 更新簇心
        double sumx1 = 0, sumy1 = 0;
        for (int i = 0; i < cluster_size[cid1]; ++i) {
            int pid = cluster_members[cid1][i];
            sumx1 += px[pid]; sumy1 += py[pid];
        }
        double new_cx1 = sumx1 / cluster_size[cid1];
        double new_cy1 = sumy1 / cluster_size[cid1];

        double sumx2 = 0, sumy2 = 0;
        for (int i = 0; i < cluster_size[cid2]; ++i) {
            int pid = cluster_members[cid2][i];
            sumx2 += px[pid]; sumy2 += py[pid];
        }
        double new_cx2 = sumx2 / cluster_size[cid2];
        double new_cy2 = sumy2 / cluster_size[cid2];

        double move = sqrt((new_cx1-cx1)*(new_cx1-cx1)+(new_cy1-cy1)*(new_cy1-cy1))
                    + sqrt((new_cx2-cx2)*(new_cx2-cx2)+(new_cy2-cy2)*(new_cy2-cy2));
        cx1 = new_cx1; cy1 = new_cy1;
        cx2 = new_cx2; cy2 = new_cy2;

        if (move <= 1e-6) break;
    }

    compute_center_sse(cid1);
    compute_center_sse(cid2);
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        cin >> px[i] >> py[i];
    }

    int cluster_count =1;
    cluster_size[0] = M;
    for (int i = 0; i < M; ++i) cluster_members[0][i] = i;
    compute_center_sse(0);

    while (cluster_count < N) {
        // 找 SSE 最大的簇
        int best_idx = 0;
        for (int i = 1; i < cluster_count; ++i) {
            if (sse[i] > sse[best_idx]) best_idx = i;
        }
        int new_cid1 = cluster_count++;
        int new_cid2 = cluster_count++;

        if (!split_cluster(best_idx, new_cid1, new_cid2)) {
            cluster_count -= 2; // 分裂失败
            break;
        }

        // 删除 old cluster
        cluster_size[best_idx] = cluster_size[new_cid1];
        for (int i = 0; i < cluster_size[new_cid1]; ++i) {
            cluster_members[best_idx][i] = cluster_members[new_cid1][i];
        }
        center_x[best_idx] = center_x[new_cid1];
        center_y[best_idx] = center_y[new_cid1];
        sse[best_idx] = sse[new_cid1];

        // 最后一个簇改成 new_cid2
        cluster_size[new_cid1] = cluster_size[new_cid2];
        for (int i = 0; i < cluster_size[new_cid2]; ++i) {
            cluster_members[new_cid1][i] = cluster_members[new_cid2][i];
        }
        center_x[new_cid1] = center_x[new_cid2];
        center_y[new_cid1] = center_y[new_cid2];
        sse[new_cid1] = sse[new_cid2];
        cluster_count--; // 实际增加了1簇

        // 输出簇大小降序
        int sizes[MAXC];
        for (int i = 0; i < cluster_count; ++i) sizes[i] = cluster_size[i];
        sort(sizes, sizes+cluster_count, greater<int>());
        for (int i = 0; i < cluster_count; ++i) {
            cout << sizes[i] << (i+1 == cluster_count ? '\n' : ' ');
        }
    }
    return 0;
}