中英文网站怎么实现,公司网站建设多少费用兴田德润在哪里,网络销售就是忽悠人,可以在什么网站做二建题目《算法竞赛快冲300题》将于2024年出版#xff0c;是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码#xff0c;以中低档题为主#xff0c;适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “
最…《算法竞赛·快冲300题》将于2024年出版是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码以中低档题为主适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “
最小生成树” 链接
http://oj.ecustacm.cn/problem.php?id1804 题目描述
【题目描述】 在平面中有n个点(xi,yi)两点之间的距离为欧几里得距离的平方。 求最小生成树的权重。 平面坐标满足(0≤xi≤1000000,0≤yi≤10) 【输入格式】 输入第一行为正整数nn不超过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根横线y0y1…y11那么n个点都会在这11根线上。当处理到第i点时只要把它和左边的11根线上的最近点连接并且把它与右边的11根线上的最近点连接即可。这样得到的边仍然会连通所有点并且保留了最短的边。这样每个点只需要连22个边总边数只有22×n条。 不过还可以简化对每个点只连它左边的11条边即可不用连右边的边请思考为什么。 处理好边后其他代码就是标准的最小生成树的模板。本题的边数不多用代码比较简单的Kruskal算法编码。 【笔记】 最小生成树。
C代码 #includebits/stdc.h
using namespace std;
#define Mul(a) ((long long)(a) * (a))
const int N 1e5 10;
typedef pairint, 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(uv) continue; //产生了圈丢弃else s[u] v, ans e[i].w;}coutansendl;
}
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 ComparableNode{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 ComparableEdge{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()
