- it
- P2504 [HAOI2006]聪明的猴子
题目
P2504 [HAOI2006]聪明的猴子
分析
kruskal算法模板
AC代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std
;
int temp
[5005], x
[5005], y
[5005], f
[5005];
struct Edge
{
int u
;
int v
;
double w
;
}edge
[1000005];
int cnt
;
int getf(int x
)
{
if (x
== f
[x
])
{
return x
;
}
int fx
= getf(f
[x
]);
return f
[x
] = fx
;
}
int cmp(Edge a
, Edge b
)
{
return a
.w
< b
.w
;
}
int merge(int u
, int v
)
{
int t1
= getf(f
[u
]);
int t2
= getf(f
[v
]);
if (t1
!= t2
)
{
f
[t1
] = t2
;
return 1;
}
return 0;
}
int main()
{
int n
, m
;
scanf("%d", &m
);
for (int i
= 1; i
<= m
; i
++)
{
scanf("%d", &temp
[i
]);
}
scanf("%d", &n
);
for (int i
= 1; i
<= n
; i
++)
{
scanf("%d%d", &x
[i
], &y
[i
]);
}
for (int i
= 1; i
<= n
; i
++)
{
f
[i
] = i
;
}
for (int i
= 1; i
<= n
; i
++)
{
for (int j
= i
+ 1; j
<= n
; j
++)
{
double w
= sqrt(pow(x
[i
] - x
[j
], 2) + pow(y
[i
] - y
[j
], 2)) ;
edge
[++cnt
] = {i
, j
, w
};
}
}
sort(edge
+ 1, edge
+ cnt
+ 1, cmp
);
int t
= 0;
double maxLength
= -1;
for (int i
= 1; i
<= cnt
; i
++)
{
if (merge(edge
[i
].u
, edge
[i
].v
))
{
t
++;
maxLength
= max(maxLength
, edge
[i
].w
);
}
if (t
== n
- 1)
{
break;
}
}
int ans
= 0;
for (int i
= 1; i
<= m
; i
++)
{
if (temp
[i
] >= maxLength
)
{
ans
++;
}
}
printf("%d\n", ans
);
return 0;
}
