P4047 [JSOI2010]部落划分 最小生成树
传送门
这题其实有两种做法：
1.
我一开始想到的是二分加并查集，考虑二分最近部落的距离，如果两点i，j距离小于等于mid那么连边，并查集维护，最后统计有多少集合。
考虑如何证明单调性：如果两点i，j在mid1情况下能连边，那么在mid2情况下也能连边（mid2>mid1），那么mid1情况下的集合数不可能小于mid2情况下的集合数
这样我们可以愉快地二分答案。
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
| #include <bits/stdc++.h>
#define MAXN 10005
using namespace std;
inline int read() {
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9') {
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9') {
x=(x*10)+(ch-'0');
ch=getchar();
}
return x*f;
}
namespace BCJ{
int fa[MAXN];
inline void Init(){
for (register int i=0;i<MAXN;++i){
fa[i]=i;
}
}
int Fa(int i){
return fa[i]==i?i:fa[i]=Fa(fa[i]);
}
inline void Union(int i,int j){
fa[Fa(i)]=Fa(j);
}
};
using namespace BCJ;
int x[MAXN],y[MAXN];
inline double Dist(int i,int j){
return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int n,k;
inline bool Check(double mid){
Init();
for (register int i=1;i<=n;++i){
for (register int j=1;j<=n;++j){
if (Dist(i,j)<=mid){
Union(i,j);
}
}
}
int ans=0;
for (register int i=1;i<=n;++i){
if (fa[i]==i) ans++;
}
return ans>=k;
}
int main(){
Init();
n=read(),k=read();
for (register int i=1;i<=n;++i){
x[i]=read(),y[i]=read();
}
double l=0,r=0x7fffffff;
const double eps=1e-4;
while (l+eps<r){
double mid=(l+r)/2.0;
if (Check(mid)) l=mid;
else r=mid;
}
printf("%.2lf\n",l);
}
|
2.
考虑连边过程中集合数的变化，发现多连一条边，集合数就会减一。
要让最后有k个集合，yy一下，发现要连n−k+1条边，于是我们可以用一个类似于Kruskal的贪心，只不过加到n−k+1条边就退出。
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
73
74
| #include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
namespace BCJ{
int fa[MAXN];
inline void Init(){
for (register int i=0;i<MAXN;++i){
fa[i]=i;
}
}
int Fa(int i){
return fa[i]==i?i:fa[i]=Fa(fa[i]);
}
inline void Union(int i,int j){
fa[Fa(i)]=Fa(j);
}
};
using namespace BCJ;
struct Edge{
int u,v;
double w;
}G[MAXN*2];
inline bool operator < (const Edge &A,const Edge &B){
return A.w<B.w;
}
int tot;
inline void AddEdge(int u,int v,double w){
G[++tot].u=u,G[tot].v=v,G[tot].w=w;
}
double x[MAXN],y[MAXN];
#define Pow(a) a*a
inline double dis(int i,int j){
return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
inline double Kruscal(int MaxE){
Init();
sort(G+1,G+1+tot);
int E=0;
for (register int i=1;i<=tot;++i){
if (Fa(G[i].u)!=Fa(G[i].v)){
Union(G[i].u,G[i].v);
E++;
if (E==MaxE){
return G[i].w;
}
}
}
}
int main(){
int n=read(),k=read();
for (register int i=1;i<=n;++i){
x[i]=(double)read();
y[i]=(double)read();
}
for (register int i=1;i<n;++i){
for (register int j=i+1;j<=n;++j){
AddEdge(i,j,dis(i,j));
}
}
printf("%.2lf\n",Kruscal(n-k+1));
}
|
p.s被double孙了甚久。
