NC24587. [USACO 2014 Mar S]Watering the Fields
描述
输入描述
* Line 1: The integers N and C.
* Lines 2..1+N: Line i+1 contains the integers xi and yi.
输出描述
* Line 1: The minimum cost of a network of pipes connecting the
fields, or -1 if no such network can be built.
示例1
输入:
3 11 0 2 5 0 4 3
输出:
46
C++(g++ 7.5.0) 解法, 执行用时: 182ms, 内存消耗: 23272K, 提交时间: 2023-04-24 15:53:56
#include<bits/stdc++.h>
#define N 5000005
using namespace std;
int n,m,fa[N],sum,cnt,a[N],b[N];
int dis,idx;
struct node{
int u,v,w;
bool operator<(const node&t)const{
return w<t.w;
}
}e[N];
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
bool unionn(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy){
fa[fy]=fx;
return 1;
}
return 0;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
for(int j=1;j<i;j++){
dis=(a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j]);
if(dis>=m){
e[++idx]={i,j,dis};
}
}
}
sort(e+1,e+idx+1);
for(int i=1;i<=idx;i++){
if(unionn(e[i].u,e[i].v)){
cnt++;
sum+=e[i].w;
}
if(cnt==n-1){
cout<<sum;
return 0;
}
}
cout<<-1<<endl;
}
C++14(g++5.4) 解法, 执行用时: 169ms, 内存消耗: 16964K, 提交时间: 2020-03-22 00:03:07
#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#include<queue>
using namespace std;
int n,c,x[2100],y[2100],cnt,te;
bool vis[2100];
long long ans;
struct nod{
int x,v;
inline bool operator <(const nod &a)const{
return v>a.v;
}
}tn;
priority_queue<nod> q;
int main(){
scanf("%d%d",&n,&c);
fo(i,1,n) scanf("%d%d",&x[i],&y[i]);
q.push((nod){1,0});
while (cnt<n&&!q.empty()){
tn=q.top();
q.pop();
if (vis[tn.x]) continue;
vis[tn.x]=1;
ans+=tn.v;
cnt++;
fo(i,1,n) if (!vis[i]){
te=(x[tn.x]-x[i])*(x[tn.x]-x[i])+(y[tn.x]-y[i])*(y[tn.x]-y[i]);
if (te>=c) q.push((nod){i,te});
}
}
if (cnt<n) printf("-1\n");//!!!!!!!!!!
else printf("%d\n",ans);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 142ms, 内存消耗: 16988K, 提交时间: 2020-03-24 10:48:23
#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#include<queue>
using namespace std;
int n,c,x[2100],y[2100],cnt,te;
bool vis[2100];
long long ans;
struct nod
{
int x,v;
inline bool operator <(const nod &a)const
{
return v>a.v;
}
}tn;
priority_queue<nod> q;
int main()
{
scanf("%d%d",&n,&c);
fo(i,1,n) scanf("%d%d",&x[i],&y[i]);
q.push((nod){1,0});
while(cnt<n&&!q.empty())
{
tn=q.top();
q.pop();
if(vis[tn.x]) continue;
vis[tn.x]=1;
ans+=tn.v;
cnt++;
fo(i,1,n)
if(!vis[i])
{
te=(x[tn.x]-x[i])*(x[tn.x]-x[i])+(y[tn.x]-y[i])*(y[tn.x]-y[i]);
if(te>=c) q.push((nod){i,te});
}
}
if(cnt<n) printf("-1\n");
else printf("%d\n",ans);
return 0;
}