《算法竞赛·快冲300题》每日一题：“最小生成树”

《算法竞赛·快冲300题》将于2024年出版，是《算法竞赛》的辅助练习册。
所有题目放在自建的OJ New Online Judge。
用C/C++、Java、Python三种语言给出代码，以中低档题为主，适合入门、进阶。

“ 最小生成树” ，链接： http://oj.ecustacm.cn/problem.php?id=1804

题目描述

【题目描述】
在平面中有n个点(xi,yi)，两点之间的距离为欧几里得距离的平方。
求最小生成树的权重。
平面坐标满足：(0≤xi≤1000000,0≤yi≤10)
【输入格式】 输入第一行为正整数n，n不超过100000。
接下来n行，每行两个整数x和y，表示坐标点(x,y)。
【输出格式】 输出一个数表示答案。
【输入样例】

10
83 10
77 2
93 4
86 6
49 1
62 7
90 3
63 4
40 10
72 0

【输出样例】

660

---

题解

   本题差不多是一道最小生成树的模板题，但是需要处理好边。本题的任意两点间有边，边的总数量约为$n^2/2$，而n最大是 $10^6$，$n^2/2$条边显然会超出空间限制。
   能否减少边的数量？注意到本题所有点的y坐标的限制是0≤yi≤10，这n个点的y坐标都在0和10之间。在平面上画11根横线；y=0，y=1，…，y=11，那么n个点都会在这11根线上。当处理到第i点时，只要把它和左边的11根线上的最近点连接，并且把它与右边的11根线上的最近点连接即可。这样得到的边，仍然会连通所有点，并且保留了最短的边。这样，每个点只需要连22个边，总边数只有22×n条。
   不过还可以简化，对每个点，只连它左边的11条边即可，不用连右边的边，请思考为什么。
   处理好边后，其他代码就是标准的最小生成树的模板。本题的边数不多，用代码比较简单的Kruskal算法编码。
【笔记】 最小生成树。

C++代码

  

#include<bits/stdc++.h>
using namespace std;
#define Mul(a) ((long long)(a) * (a))
const int N = 1e5 + 10;
typedef pair<int, int> Node;
int n, m;         //点、边
Node a[N];        //n个点的坐标
struct edge{int u, v;long long w;
}e[N * 22];           //边的数量。如果只连左边的11条边，这里改为N*11
bool cmp(edge a, edge b){ return a.w < b.w;}    //从小到大排序
void add_edge(int u, int v) {  //点u和点v连边m++;e[m].u = u;e[m].v = v;e[m].w = Mul(a[u].first - a[v].first) + Mul(a[u].second - a[v].second);
}
int s[N];//并查集
int find_set(int x){      //查询并查集，返回x的根if(x != s[x])s[x] = find_set(s[x]);     //路径压缩return s[x];
}
void kruskal(){for(int i = 1; i <= n; i++)  s[i] = i;    //并查集初始化sort(e + 1, e + 1 + m,cmp);               //边排序long long ans = 0;for(int i = 1; i <= m; i++){              //从小到大遍历边，加入到最小生成树int u = find_set(e[i].u), v = find_set(e[i].v);if(u==v) continue;                    //产生了圈，丢弃else  s[u] = v, ans += e[i].w;}cout<<ans<<endl;
}
int Last[15];
int main(){cin >> n;for(int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;sort(a + 1, a + 1 + n);                    //对点排序。实际是对x从小到大排序//每个点往每行的左边最近点连边for(int i = 0; i <= 10; i++)   Last[i] = 0;for(int i = 1; i <= n; i++) {for(int y = 0; y <= 10; y++)if(Last[y])   add_edge(i, Last[y]);Last[a[i].second] = i;}//每个点往每行的右边最近点连边。可以省略/* for(int i = 0; i <= 10; i++)Last[i] = 0;for(int i = n; i >= 1; i--) {for(int y = 0; y <= 10; y++)if(Last[y])   add_edge(i, Last[y]);Last[a[i].second] = i;}*/kruskal();return 0;
}

Java代码

import java.util.*;public class Main {static class Node implements Comparable<Node>{int x, y;Node(int x, int y) {this.x = x;this.y = y;}public int compareTo(Node o) {return Integer.compare(this.x, o.x);}}static class Edge implements Comparable<Edge>{int u, v;long w;Edge(int u, int v, long w) {this.u = u;this.v = v;this.w = w;}public int compareTo(Edge o) {return Long.compare(this.w, o.w);}}static final int N = 1_00_005;static Node[] a = new Node[N];static Edge[] e = new Edge[N * 11];static int[] s = new int[N];static int[] Last = new int[15];static int n, m;static long mul(int a) {  return (long)a * a; }static void addEdge(int u, int v) {m++;e[m] = new Edge(u, v, mul(a[u].x - a[v].x) + mul(a[u].y - a[v].y));}static int findSet(int x) {if (x != s[x])s[x] = findSet(s[x]);return s[x];}static void kruskal() {for (int i = 1; i <= n; i++) s[i] = i;Arrays.sort(e, 1, m + 1);long ans = 0;for (int i = 1; i <= m; i++) {int u = findSet(e[i].u), v = findSet(e[i].v);if (u == v) continue;s[u] = v;ans += e[i].w;}System.out.println(ans);}public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();for (int i = 1; i <= n; i++) {int x = sc.nextInt(), y = sc.nextInt();a[i] = new Node(x, y);}Arrays.sort(a, 1, n + 1);for (int i = 0; i <= 10; i++) Last[i] = 0;for (int i = 1; i <= n; i++) {for (int y = 0; y <= 10; y++) if (Last[y] > 0) addEdge(i, Last[y]);Last[a[i].y] = i;}kruskal();}
}

Python代码

from typing import List, Tuple
def mul(b):  return b * b
class Node:def __init__(self, x: int, y: int):self.x = xself.y = ydef __lt__(self, other: "Node") -> bool:return self.x < other.x
class Edge:def __init__(self, u: int, v: int, w: int):self.u = uself.v = vself.w = wdef __lt__(self, other: "Edge") -> bool:return self.w < other.w
N = 100005
a: List[Node] = [Node(0, 0) for i in range(N)]
e: List[Edge] = [Edge(0, 0, 0) for i in range(N * 11)]
s: List[int] = [i for i in range(N)]
Last: List[int] = [0] * 15
n = m = 0
def addEdge(u: int, v: int) -> None:global mm += 1e[m].u = ue[m].v = ve[m].w = mul(a[u].x - a[v].x) + mul(a[u].y - a[v].y)def findSet(x: int) -> int:global sif x != s[x]:  s[x] = findSet(s[x])return s[x]def kruskal() -> None:global n, m, s, efor i in range(1, n + 1):  s[i] = ie[1:] = sorted(e[1:m + 1])ans = 0for i in range(1, m + 1):u = findSet(e[i].u)v = findSet(e[i].v)if u == v:  continues[u] = vans += e[i].wprint(ans)
if __name__ == "__main__":n = int(input())for i in range(1, n + 1):x, y = map(int, input().split())a[i] = Node(x, y)a[1:] = sorted(a[1:n + 1])Last = [0] * 15for i in range(1, n + 1):for y in range(11):if Last[y] > 0:  addEdge(i, Last[y])Last[a[i].y] = ikruskal()