Arctic Network

C++(g++ 7.5.0) 解法, 执行用时: 11ms, 内存消耗: 4408K, 提交时间: 2022-08-20 14:53:52

#include<bits/stdc++.h>
using namespace  std;
#define MAXN 2500
#define MAXM 200000
typedef pair<int,int> pii;
#define dis(x,y)  (sqrt(pow((nod[x].x-nod[y].x),2)+pow((nod[x].y-nod[y].y),2)))
struct {
    double x,y;
}nod[MAXN];
const int inf = 0x3f3f3f3f;
double edge[MAXN][MAXN];
bool used[MAXN]={0};
double d[MAXN];
vector<double> ans;
void prim(int n)
{
    for(int i=1;i<=n;i++)
        d[i]=99999999;
    memset(used,0,sizeof(used));
    d[1]=0;
    for(int i=1;i<n;i++)
    {
        int x=0;
        for(int j=1;j<=n;j++)
            if(!used[j]&&(x==0||d[x]>d[j]))
                x=j;
        used[x]=true;
        for(int y=1;y<=n;y++)
            if(!used[y])d[y]=min(d[y],edge[x][y]);
    }
    for(int i=1;i<=n;i++)
        ans.push_back(d[i]);
}
int momey[MAXN];
int main(){
    int tot;scanf("%d",&tot);
    while(tot--) {
        int m,n;
        scanf("%d%d", &m,&n);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                edge[i][j]=999999;
            }
        for(int i=1;i<=n;i++){
            scanf("%lf%lf",&nod[i].x,&nod[i].y);
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                int x=i,y=j;
                    edge[i][j]=edge[j][i]=dis(x,y);
            }
        prim(n);
        sort(ans.begin(),ans.end());
        
        printf("%.2lf\n", ans[n-m]);
        ans.clear();
    }
}

C++14(g++5.4) 解法, 执行用时: 87ms, 内存消耗: 6492K, 提交时间: 2020-02-15 16:28:44

#include<bits/stdc++.h>
using namespace std;
const int N=600;
struct Edge{
    Edge(int x,int y,int len2):x(x),y(y),len2(len2){}
    bool operator<(const Edge &t){return len2<t.len2;}
    int x,y,len2;
};
int fa[N],x[N],y[N];
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
int dis2(int i,int j){return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);}

int main(){
    int t,s,p;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&s,&p);
        for(int i=1;i<=p;++i){
            fa[i]=i;
            scanf("%d%d",x+i,y+i);
        }
        vector<Edge> e;
        for(int i=1;i<=p;++i)
            for(int j=1;j<=p;++j)
                if(i!=j)e.push_back(Edge(i,j,dis2(i,j)));
        sort(e.begin(),e.end());
        double ans;
        for(Edge &t:e){
            int u=get(t.x),v=get(t.y);
            if(u==v)continue;
            fa[u]=v;
            if(--p==s){
                ans=sqrt(t.len2);
                break;
            }
        }
        printf("%.2f\n",ans);
    }
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 28ms, 内存消耗: 6372K, 提交时间: 2022-10-16 12:33:21

#include<bits/stdc++.h>
using namespace std;
#define int long long
int s,p;
int x[505],y[505];
int f[505];

int find(int x){
	if(x==f[x]){
		return x;
	}else{
		return f[x]=find(f[x]);
	}
}
int t;
signed main()
{
    cin>>t;
    while(t--){
	cin>>s>>p;
	priority_queue<pair<double,pair<int,int> > > q;
	for(int i=0;i<p;i++){
		cin>>x[i]>>y[i];
		f[i]=i;
	}
	for(int i=0;i<p;i++){
		for(int j=i+1;j<p;j++){
			double tg=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
			q.push(make_pair(-1*tg,make_pair(i,j)));
			//cout<<tg<<endl;
		}
	}
	int k=p-s;
	int n;
	if(k==0) printf("0.00\n");
	while(k){
		double tg=q.top().first;
		int x=q.top().second.first;
		int y=q.top().second.second;
		//cout<<" "<<tg<<endl;
		q.pop();
		int fx=find(x);
		int fy=find(y);
		if(fy!=fx){
			f[fx]=fy;
			k--;
			//cout<<"k="<<k<<endl;
			if(k==0){
				printf("%.2lf\n",-1*tg);
			}
		}
	}
    }
	return 0;
}

详情