解题思路与题意分析

题意分析

Flatopia岛国需要建设高速公路使所有城镇连通，要求新建高速公路的总长度最小。已知：

• 城镇坐标已知，高速公路长度为两点间欧氏距离
• 已有部分高速公路，需计算还需新建的高速公路
• 输出新建高速公路的连接城镇对，按最小生成树规则选择

解题思路

这是典型的最小生成树(MST)问题，使用Kruskal算法解决：

1. 计算所有城镇间的距离作为候选边
2. 将已有高速公路设为权重0的边（优先保留）
3. 按边权排序后用并查集选取边，构建最小生成树
4. 输出生成树中权重>0的边（即需要新建的高速公路）

标程

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 750 + 10;
const int MAXM = 500000;

struct Edge {
    int u, v, dist;
    Edge() {}
    Edge(int u, int v, int d) : u(u), v(v), dist(d) {}
    bool operator<(const Edge& rhs) const {
        return dist < rhs.dist;
    }
};

struct Kruskal {
    int n, m;
    Edge edges[MAXM];
    int fa[MAXN];
    
    int findset(int x) {
        return fa[x] == -1 ? x : fa[x] = findset(fa[x]);
    }
    
    void init(int n) {
        this->n = n;
        m = 0;
        memset(fa, -1, sizeof(fa));
    }
    
    void addEdge(int u, int v, int dist) {
        edges[m++] = Edge(u, v, dist);
    }
    
    void kruskal() {
        sort(edges, edges + m);
        int cnt = 0;
        for (int i = 0; i < m && cnt < n - 1; i++) {
            int u = edges[i].u, v = edges[i].v;
            int fu = findset(u), fv = findset(v);
            if (fu != fv) {
                if (edges[i].dist > 0) {
                    printf("%d %d\n", u, v);
                }
                fa[fu] = fv;
                cnt++;
            }
        }
    }
} kruskal;

struct Point {
    int x, y;
} p[MAXN];

int getDistance(int i, int j) {
    int dx = p[i].x - p[j].x;
    int dy = p[i].y - p[j].y;
    return dx * dx + dy * dy;
}

int main() {
    int n, m;
    while (scanf("%d", &n) == 1) {
        kruskal.init(n);
        for (int i = 1; i <= n; i++) {
            scanf("%d %d", &p[i].x, &p[i].y);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                kruskal.addEdge(i, j, getDistance(i, j));
            }
        }
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            kruskal.addEdge(u, v, 0);
        }
        kruskal.kruskal();
    }
    return 0;
}

代码解析

1. 数据结构设计：

   • Edge结构体存储边的两个顶点和距离
   • Kruskal结构体封装算法逻辑，包含并查集操作
   • Point结构体存储城镇坐标

2. 核心算法流程：

   • 计算所有城镇间距离作为候选边
   • 将已有高速公路设为权重0的边（优先保留）
   • 按边权排序后，用并查集判断连通性
   • 选取边构建生成树，输出权重>0的新建边

3. 优化细节：

   • 计算距离平方避免浮点运算
   • 并查集路径压缩优化查找效率
   • 提前终止条件（当选取n-1条边时停止）

该代码通过Kruskal算法高效解决了最小生成树问题，时间复杂度为O(M log M)，其中M为边数，适用于题目给定的数据范围。