为什么只能过样例呢//劳动节快乐!
查看原帖
为什么只能过样例呢//劳动节快乐!
272531
只狼楼主2020/5/1 17:41
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
struct node{
	int q,z;
	double r;
};
int m,n,f[1007];
double sum;
struct node a[1000007];
int find(int x){
	if(x==f[x]) return x;
	f[x]=find(f[x]);
	return f[x];
}
bool cmp(struct node x,struct node y){
	if(x.r<y.r) return true;
	else return false;
}
void kk(int l);
int main(){
	int i,j;
	cin>>n>>m;
	int c[1006][2];
	for(i=1;i<=n;i++){
		cin>>c[i][0]>>c[i][1];
		f[i]=i;
	}
	int l=0,x,y;
	for(i=1;i<=n;i++){
		for(j=i+1;j<=n;j++){
				a[l].q=i;
				a[l].z=j;
				x=c[i][0]-c[j][0];
				y=c[i][1]-c[j][1];
				a[l].r=(double)sqrt((double)x*x*1.0+(double)y*y);
				l++;
		}
	}
	for(i=l;i<l+m;i++){
		cin>>x>>y;
		a[i].q=x;
		a[i].z=y;
		a[i].r=0.0;
	}
	sort(a,a+l+m,cmp);
	kk(l+m);
	printf("%.2lf",sum);
	return 0;
} 
void kk(int l){
	int x,y,i,q=1;
	for(i=0;i<l;i++){
		x=find(a[i].q);
		y=find(a[i].z);
		if(x==y) continue;
		sum+=a[i].r;
		q++;
		if(q==n) break;
	}
}
2020/5/1 17:41
加载中...