《算法竞赛·快冲300题》将于2024年出版，是《算法竞赛》的辅助练习册。
所有题目放在自建的OJ New Online Judge。
用C/C++、Java、Python三种语言给出代码，以中低档题为主，适合入门、进阶。
文章目录
- 题目描述
- 题解
- 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^2/2
n2/2，而n最大是
1
0
6
10^6
106，
n
2
/
2
n^2/2
n2/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 = x
self.y = y
def __lt__(self, other: "Node") -> bool:
return self.x < other.x
class Edge:
def __init__(self, u: int, v: int, w: int):
self.u = u
self.v = v
self.w = w
def __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 m
m += 1
e[m].u = u
e[m].v = v
e[m].w = mul(a[u].x - a[v].x) + mul(a[u].y - a[v].y)
def findSet(x: int) -> int:
global s
if x != s[x]: s[x] = findSet(s[x])
return s[x]
def kruskal() -> None:
global n, m, s, e
for i in range(1, n + 1): s[i] = i
e[1:] = sorted(e[1:m + 1])
ans = 0
for i in range(1, m + 1):
u = findSet(e[i].u)
v = findSet(e[i].v)
if u == v: continue
s[u] = v
ans += e[i].w
print(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] * 15
for i in range(1, n + 1):
for y in range(11):
if Last[y] > 0: addEdge(i, Last[y])
Last[a[i].y] = i
kruskal()
