题解：P8191 [USACO22FEB] Moo Network G

· · 题解

题目传送门:P8191 [USACO22FEB] Moo Network G

题目大意:

一共有 n 头牛，给你它的位置，x_i 和 y_i。两头牛的交流成本是欧几里得距离的平方。求，最低的成本。

分析：

首先，看到“最低成本”这几个字，立马反应，这是一道题的考点是最小生成树。

这里应该有两个排序，一个是把坐标从小到大排序，另一个是把距离从小到大排序。

这里还需要存个图，v 代表的是两者间的距离。

思路：

用 Kruskal，因为这个好写一点。

然后，它的权值是距离，距离计算用一个 dist 函数计算就好啦。

用一个 struct 类型的数组g[]存图，g[].x和g[].y存位置，g[].v存距离。用一个 m 存边。到时候排序的时候不是g+n+1，而是g+m+1。

向左找 30 个点连边不会错。因为 y\le10 ，所以最小生成树的边，都在这里面建的边当中。

注意：

题目说是欧几里德距离的平方，前面就不需要写 sqrt 了。也不用 double 了。

然后要开 long long ，不然只有 10 分。

最优的话是连 n-1 条边。

最后代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,M=4e6+5;
#define int long long
int n,m;
int fa[N];
int cnt,ans;
struct node
{
int x,y,v;
}g[M];//它存的是图,所以范围要大一些
struct Node
{
int x,y;
}a[N];
int find(int x)//这里是找自己的根节点
{
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
void un(int x,int y)//这里是合并
{
x=find(x),y=find(y);
if(x!=y)
fa[x]=y;
return ;
}
bool cmp(node q,node p)//将距离从小到大排序
{
return q.v<p.v;
}
bool Cmp(Node q,Node p)//将位置从小到大排序
{
if(q.x!=p.x)
return q.x<p.x;
return q.y<p.y;
}
void k()//kruskal啦,只是太长不想打那么多而已
{
for(int i=1;i<=n;i++)//初始化,一开始每个人的根节点都是自己
fa[i]=i;
sort(g+1,g+m+1,cmp);//距离排序
cnt=ans=0;//保险起见,初始值为0
for(int i=1;i<=m;i++)//注意!这里不是n
{
if(find(g[i].x)!=find(g[i].y))//看它们有没有合并过
{
un(g[i].x,g[i].y);//合并
ans+=g[i].v;//加上距离,也就是成本
cnt++;//代表连的边+1
}
if(cnt==n-1)//一般是只有n-1条边( 最优),不过不写也没关系
return ;
}
return ;
}
double dist(int x1,int y1,int x2,int y2)
{
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);//这里是欧几里得算法距离的平方,也就是成本
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y;//输入位置
sort(a+1,a+n+1,Cmp);//将位置从小到大排序
for(int i=1;i<=n-1;i++)
{
for(int j=i;j<=i+30;j++)//这里是为了保险,加了30意思是连它前30个点
{
m++;//这里4行是存图
g[m].x=i;
g[m].y=j;
g[m].v=dist(a[i].x,a[i].y,a[j].x,a[j].y);
}
}
k();//调用函数
cout<<ans;//也可以在k函数里面输出
return 0;
}