P7991 [USACO21DEC] Connecting Two Barns S
思路
并查集+二分查找
以下假设点 i 所在的连通块的点集为 Gi。有可能存在 Gu=Gv。
具体做法是分类讨论：
- 不连边，则必须保证 G1=Gn。
- 连一条边，则在分别在 G1 和 Gn 中找一点连边。
- 连两条边，则寻找一点 x。接着在 Gx 中枚举一点 y。将 y 与 G1 中一点连边，再将 y 与 Gn 中一点连边。
接下来定义一个函数：cost(u,v)。它的操作就是在 Gu 中枚举一点 y。将 y 与 Gv 中一点连边的最小代价。
连边操作可以通过二分查找与 y 权值差最小的点 O(logn) 实现。
所以，上述所有情况都可归为：枚举一点 x，代价和就是 cost(1,x)+cost(x,n)。算出所有代价和，取最小值即为答案。可以这样做的具体原因请读者自行思考。
注意
因为此题数据有些特殊，必须保证程序的时间复杂度是 O(nlogn)。只需稍稍修改一下 cost(u,v) 函数，保证在较小的块中枚举，和较大的块中的点连边即可。我就是这样50分的
代码
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include<bits/stdc++.h>
using namespace std;
long long n,m,fa[1000005];
void init()
{
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
}
long long find(long long x)
{
if(fa[x]==x)
{
return x;
}
else
{
return fa[x]=find(fa[x]);
}
}
void merge(long long x,long long y)
{
x=find(x);
y=find(y);
if(x!=y)
{
fa[x]=y;
}
}
long long dist(long long c,long long d)
{
return (c-d)*(c-d);
}
vector<long long>dot[1000005];
long long cost(long long fx,long long fy)
{
if(dot[fx].size()>dot[fy].size())
{
swap(fx,fy);
}
long long res=1e18;
for(int i=0;i<dot[fx].size();i++)
{
long long u=dot[fx][i];
long long bg=lower_bound(dot[fy].begin(),dot[fy].end(),u)-dot[fy].begin();
if(bg>0)
{
long long v=dot[fy][bg-1];
res=min(res,dist(u,v));
}
if(bg<dot[fy].size())
{
long long v=dot[fy][bg];
res=min(res,dist(u,v));
}
}
return res;
}
int main()
{
long long t;
cin>>t;
while(t--)
{
cin>>n>>m;
init();
for(int i=1;i<=n;i++)
{
dot[i].clear();
}
for(int i=1;i<=m;i++)
{
long long x,y;
cin>>x>>y;
merge(x,y);
}
for(int i=1;i<=n;i++)
{
long long tmp=find(i);
dot[tmp].push_back(i);
}
long long ans=1e18;
long long st=find(1),ed=find(n);
for(int i=1;i<=n;i++)
{
ans=min(ans,cost(st,i)+cost(ed,i));
}
cout<<ans<<endl;
}
}
|
