题解：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$ 条边。

最后代码

CPP

#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;
}

题解：P8191 [USACO22FEB] Moo Network G

文章操作

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

题目大意:

分析：

思路：

注意：

最后代码

相关推荐

评论

题解：P8191 [USACO22FEB] Moo Network G