18分 , 其他MLE , 代码求调
查看原帖
18分 , 其他MLE , 代码求调
774204
A_chicken_boy楼主2023/8/13 15:57
#include <bits/stdc++.h>
using namespace std ;
#define leng 20000001
struct A{
	int x , y ;
	long long dis ;
}edge[leng];
int tot ;
int x[leng] , y[leng] ;
int fa[leng] ;
int n ;
long long abc ( int , int ) ;
bool cmp ( A a , A b );
int get ( int x ) ;
int main ( ){
	cin >> n ;
	for ( int i = 1 ;i <= n ; ++i ){
		cin >> x[i] >> y[i] ;
		fa[i] = i ;
	}
	for ( int i = 1 ; i <= n ; ++i ){
		for ( int j = i+1 ; j <= n ; ++j ){
			edge[++tot].x = i ;
			edge[tot].y = j ;
			edge[tot].dis = abc ( i , j ) ;
		}
	}
	sort ( edge + 1 , edge + 1 + tot , cmp ) ;
	long long ans = 0 ;
	for ( int i = 1 ; i <= tot ; ++i ){
		if ( get ( edge[i].x ) != get ( edge[i].y ) ){
			fa[get(edge[i].x)] = fa[get(edge[i].y)] ;
			ans += edge[i].dis ;
		}
		int f = 0;
		for ( int j = 1 ; j < n ; ++j ){
			if ( get ( j ) != get(j+1) ){
				f=1 ;
				break ;
			}
		}
		if ( !f ) break ;
	}
	cout << ans ;
	return 0 ;
}
long long abc ( int i , int j ){
	return (long long)((long long) (x[i]-x[j]) * (long long)(x[i]-x[j]) + (long long)( y[i] - y[j] ) *(long long) ( y[i] - y[j] ) ) ; 
}
bool cmp ( A a , A b ){
	return a.dis < b.dis ;
}
int get ( int x ){
	if ( fa[x] == x ) return x ;
	return get ( fa[x] ) ;
}
2023/8/13 15:57
加载中...