[USACO16DEC]Moocast(gold)奶牛广播-金 题解

题解"/>

[USACO16DEC]Moocast(gold)奶牛广播-金 题解

题目链接
洛谷P2847
bzoj4744

简化题面
给你n个点，可以在任意两点间连边，代价为两点间的距离。在保证图联通的情况下，最小化最大边权。输出最小的最大边权的平方。

思路
有题解说可以用二分答案，可我不会怎么办？其实并不用二分答案，最小生成树就行，输出最小生成树的最大边权。

证明（自己瞎写的，不一定完善 应该是一定不）
首先，树保证了连通，对于任何一幅图，去掉一些边后变成树，它依然满足条件，而且答案一定不会更大。
第二，最小生成树是不停地找最小的边，那么它最大的边权一定会被最小化。如果最大边权可以更小，那它就不是最小生成树。反之，如果它是最小生成树，那么最大的边权就不会更小。所以，最小生成树的最大边权就是答案。

实现
最小生成树一般有两种找法，Kruskal算法和Prim算法。由于任意两点间都可以连边，所以选择Prim算法更好。
在算两点之间距离时有一个小技巧，不要存他们的距离，而是存他们的距离的平方，这样不会影响答案，却可以避免玄学的精度判断，写起来也简单一些。

code：

#include<cstdio>
#include<cstring>
//map存两点间的距离，x、y为读入的坐标，dis为每个点到原生成树集合距离的平方，f为每个点是否在原生成树集合内
int map[1010][1010],x[1010],y[1010],dis[1010],f[1010];
int main()
{int n,ans=0;scanf("%d",&n);for(int i=1;i<=n;i++)//读入、构图{scanf("%d%d",x+i,y+i);for(int j=1;j<i;j++)map[i][j]=map[j][i]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);}//初始化每个点到原生成树集合的距离memset(dis,0x3f,sizeof(dis));dis[1]=0;for(int i=1;i<=n;i++){int minn=0x3f3f3f3f,minj;for(int j=1;j<=n;j++)\\寻找最小距离if(!f[j]&&dis[j]<minn){minn=dis[j];minj=j;}//更新答案并标记距离最小点ans=ans>minn?ans:minn;f[minj]=1;for(int j=1;j<=n;j++)//更新距离if(!f[j]&&dis[j]>map[minj][j])dis[j]=map[minj][j];}printf("%d\n",ans);//ans即为最大边权的平方
}