NC24114. [USACO 2016 Dec G]Moocast
描述
Instead of mooing at each-other over long distances, the cows decide to equip themselves with walkie-talkies, one for each cow. These walkie-talkies each have a limited transmission radius, but cows can relay messages to one-another along a path consisting of several hops, so it is not necessary for every cow to be able to transmit directly to every other cow.
The cows need to decide how much money to spend on their walkie-talkies. If they spend X, they will each get a walkie-talkie capable of transmitting up to a distance of X−−√X. That is, the squared distance between two cows must be at most X for them to be able to communicate.
Please help the cows determine the minimum integer value of X such that a broadcast from any cow will ultimately be able to reach every other cow.
输入描述
The first line of input contains N.
The next N lines each contain the x and y coordinates of a single cow. These are both integers in the range 0…25,000.
输出描述
Write a single line of output containing the integer X giving the minimum amount the cows must spend on walkie-talkies.
示例1
输入:
4 1 3 5 4 7 2 6 1
输出:
17
C++(g++ 7.5.0) 解法, 执行用时: 131ms, 内存消耗: 16048K, 提交时间: 2022-08-06 23:04:27
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 1e3+3;
int n, x[maxn], y[maxn], cnt, tot, f[maxn];
double Ans;
struct Edge{
int u, v;
double w;
}ed[maxn * maxn];
inline bool cmp(Edge a, Edge b){
return a.w < b.w;
}
inline int find(int x){
if(x == f[x])
return x;
else
return f[x]=find(f[x]);
}
inline void Kruskal(){
for(int i=1; i<=n; i++)
f[i] = i;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(i != j){
++cnt;
ed[cnt].u = i;
ed[cnt].v = j;
ed[cnt].w = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
}
}
sort(ed+1, ed+1+cnt, cmp);
for(int i=1; i<=cnt; i++) {
int xx=find(ed[i].u),yy=find(ed[i].v);
if(xx != yy){
f[xx]=find(yy);
tot++;
Ans=ed[i].w;
}
if(tot == n-1)
break;
}
}
int main(){
cin>>n;
for(int i=1; i<=n; i++)
cin>>x[i]>>y[i];
Kruskal();
printf("%.0lf",Ans*Ans);
}
C++14(g++5.4) 解法, 执行用时: 58ms, 内存消耗: 6180K, 提交时间: 2020-10-20 11:36:33
#include <cstdio>
#include <algorithm>
#define sqr(x) ((x) * (x))
const int maxn = 1010;
const int maxm = maxn * maxn;
int x[maxn], y[maxn];
struct e {
int u, v, w;
bool inline operator < (const e &rhs) const {
return w < rhs.w;
}
} a[maxm];
int p[maxn];
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
int main() {
static int n, m, ans;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) p[i] = i;
for (int i = 1; i <= n; ++i) scanf("%d%d", x + i, y + i);
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
a[++m] = (e){i, j, sqr(x[i] - x[j]) + sqr(y[i] - y[j])};
}
}
std::sort(a + 1, a + m + 1);
for (int i = 1; i <= m; ++i) {
int fu = find(a[i].u), fv = find(a[i].v);
if (fu ^ fv) {
p[fu] = fv, ans = std::max(ans, a[i].w);
}
}
printf("%d\n", ans);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 11ms, 内存消耗: 4472K, 提交时间: 2020-10-20 14:57:26
#include<bits/stdc++.h>
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);
}