USACO22FEB Moo Network G

洛谷P8191 [USACO22FEB] Moo Network G

题目大意

有$n$个点，第$i$个点的位置为$(x_i,y_i)$，其中$0\le x_i\le 10^6,0\le y_i\le 10$。连接两个点$i,j$的成本是$(x_i-x_j{)}^2+(y_i-y_j{)}^2$，求能使这$n$个点连通的最小成本。

$1\le n\le 10^5$

题解

观察数据范围发现，$y$的范围不超过$10$，而连最短的边显然更优，所以对于每个点，我们可以将其与距离其较近的点连边，然后在这些边中做$\text{kruskal}$即可。

先将点按横坐标从小到大排序，横坐标相同的按纵坐标排序，然后对于每个点，向左找$30$个点连边，再在这些边中做$\text{kruskal}$。因为$y$的范围不超过$10$，所以最小生成树中的边一般都在上面建的这些边中。

时间复杂度为$O(30n\log n)$。

code

#include
using namespace std;
int n,v1=0,fa[100005];
long long ans=0;
struct node{
	int x,y;
}w[100005];
struct line{
	int x,y;
	long long dis;
}v[3000005];
bool cmp1(node ax,node bx){
	if(ax.x!=bx.x) return ax.x<bx.x;
	return ax.y<bx.y;
}
bool cmp2(line ax,line bx){
	return ax.dis<bx.dis;
}
long long dis(int i,int j){
	return 1ll*(w[i].x-w[j].x)*(w[i].x-w[j].x)+1ll*(w[i].y-w[j].y)*(w[i].y-w[j].y);
}
int find(int ff){
	if(fa[ff]!=ff) fa[ff]=find(fa[ff]);
	return fa[ff];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&w[i].x,&w[i].y);
		fa[i]=i;
	}
	sort(w+1,w+n+1,cmp1);
	for(int i=1;i<=n;i++){
		for(int j=max(i-30,1);j<i;j++){
			v[++v1]=(line){i,j,dis(i,j)};
		}
	}
	sort(v+1,v+v1+1,cmp2);
	for(int i=1;i<=v1;i++){
		int r1=find(v[i].x),r2=find(v[i].y);
		if(r1!=r2){
			fa[r1]=r2;
			ans+=v[i].dis;
		}
	}
	printf("%lld",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49