P8191 [USACO22FEB] Moo Network G

题目描述

农夫约翰有 $N$ 头牛（$1\le N\le 10^5$） 它们在农场里分布的极其的远，因此希望你建立一个通讯网络，便于它们更容易地交换电子短信（当然，这些短信都包含 moo 的变形体，即数字）

第 $i$ 头牛位于位置 $(x_i，y_i)$ 其中 $0\le x\le 10^6$, $0\le y\le 10$. 在牛 $i$ 与牛 $j$ 之间建立通信链路的成本是它们之间的欧几里德距离的平方，即 $(x_i-x_j{)}^2+(y_i-y_j{)}^2$

请聪明的你构建一个所有奶牛都能交流的最低成本的通信网络。如果两头奶牛通过一条链接直接连接或者它们的信息可以沿着一条链接传播，那么认为他们可以通信。

注意 此问题时间限制为4秒

输入格式

第一行输入为 $N$，接下来 $N$ 行分别描述奶牛的位置 $(x,y)$ 均为整数

输出格式

请输出允许所有奶牛通信的网络的最低成本。请注意，此开销可能太大，无法放入 32 位整数中，并且可能需要使用 64 位整数（例如，C++中的“long long”）。

输入输出样例 #1

输入 #1

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

输出 #1

660

说明/提示

测试点 2~3 满足 $N\le 1000$。

测试点 4~15 没有特殊限制。

C++实现

#include <cstdio>
#include <algorithm>
#define N 100010
#define ll long long
int n,m,fa[N],f[11];
ll ans;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x, int y,ll w){
    if(find(x)!=find(y))     {
        fa[find(x)]=find(y);
        ans+=w;
    }
}
struct edge{
	int from,to; ll w;
	bool operator<(edge b) const {return w<b.w;}
}e[N*50];

void kruskal(){
	for(int i=1;i<=n;i++) fa[i]=i;
	std::sort(e,e+m);
	for(int i=0;i<m;i++) merge(e[i].from,e[i].to,e[i].w);
}

struct oo{int x;int y;bool operator<(oo b)const{return x<b.x;}}a[N];
#define sq(x) (ll)(x)*(x)
inline ll calc(int x, int y) {return sq(a[x].x-a[y].x)+sq(a[x].y-a[y].y);}
void run(int x){
	for(int j=0;j<=10;j++) if(f[j])
		e[m++]=edge{f[j],x,calc(x,f[j])};
	f[a[x].y]=x;
}
int main(){
	scanf("%d", &n);
	for(int i=1;i<=n;i++) scanf("%d%d", &a[i].x, &a[i].y);
	std::sort(a+1,a+1+n);
	f[a[1].y]=1;
	for(int i=2;i<=n;i++) run(i);
	
	for(int i=0;i<=10;i++) f[i]=0;
	f[a[n].y]=n;
	for(int i=n-1;i>=1;i--) run(i);
	kruskal();
	printf("%lld",ans);
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容