P2872

我的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=1000001;
double ans;
int f[maxn],n,m;
struct loc{//坐标存储
int x;int y;
}loc[maxn];
struct node{//点距
int x;int y;double val;
}g[maxn];
bool comp(node a,node b){
if(a.val==b.val){
return a.x<b.x;
}
return a.val<b.val;
}
int find(int x){//找爹
if(f[x]==x) return x;
else return f[x]=find(f[x]);
}
void merge(int x,int y)//合并
{
f[find(x)]=find(y);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){//初始化
f[i]=i;
}
for(int i=1;i<=n;i++){//存坐标
int x,y;cin>>x>>y;
loc[i].x=x;loc[i].y=y;
}
int k=1;//有距边数统
for(int i=1;i<=n;i++){//计算距离
for(int j=i+1;j<=n;j++){
g[k].x=i;g[k].y=j;
g[k].val=1.0*sqrt(1.0*(loc[i].x-loc[j].x)*(loc[i].x-loc[j].x)+1.0*(loc[i].y-loc[j].y)*(loc[i].y-loc[j].y));
k++;
}
}

for(int i=1;i<=m;i++){//已有边设零 !
int a,b;
cin>>a>>b;
g[++k].x=a;g[k].y=b;g[k].val=0;
}
/*
for(int i=1;i<=n*n;i++){//调试输出
cout<<"val:"<<g[i].val<<"lcox:"<<g[i].x<<"locy"<<g[i].y<<endl;
}
*/
sort(g+1,g+1+k,comp);
int top=0;
for(int i=1;i<=k;i++) {//模板,最小生成树
if(find(g[++top].x)!=find(g[top].y)){
ans+=g[top].val;
merge(g[top].x,g[top].y);
}
}
printf("%.2lf",ans);
}

老师的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
const int maxn=1001;
int n,m,f[maxn],tot;
bool vis[1001][1001];
struct node
{
int x,y;
}g[maxn];
struct tree
{
int x,y;double d;
}tr[1000007];
double dis(int x1,int y1,int x2,int y2)
{
return (double)sqrt((double)(x2-x1)*(x2-x1)+(double)(y2-y1)*(y2-y1));
}
double ans;
bool comp(tree &a,tree &b)
{
if(a.d==b.d)
return a.x<b.x;
return a.d<b.d;
}
int find(int x)
{
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
void krucal()
{
for(int i=1;i<=tot;i++)
{
int x1=tr[i].x,y1=tr[i].y;
int a1=find(x1),b1=find(y1);
if(a1!=b1)
{
f[a1]=b1;
ans+=tr[i].d;
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=n;i++)
{
cin>>g[i].x>>g[i].y;
}
for(int i=1;i<=m;i++)
{
int x,y;cin>>x>>y;vis[x][y]=1,vis[y][x]=1;
int a=find(x),b=find(y);
if(a!=b) f[a]=b;
}
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(vis[i][j]==0)
tr[++tot].x=i,tr[tot].y=j,tr[tot].d=dis(g[i].x,g[i].y,g[j].x,g[j].y);
}
}
sort(tr+1,tr+1+tot,comp);
krucal();
printf("%.2lf",ans);
return 0;
}