Cansult's blog

即使愿望永远无法实现
我也不愿就这样放手

0%

翻车笔记 ZROI336. [18 提高 4]的 [清奇脑回路, 二分, 并查集, 最小生成树]

Posted on Edited on In

有点像最小割的感觉...

懵逼的 题目

淦

扯淡的 题解

一开始想搞个对偶图最大生成树然后跑个LCA云云的做法...

题解有两种做法...

一个是二分可能的最大值, 把能"拦下"这个球的两个点之间连边, 然后用并查集判断一下上下边界是否联通就行了

第二个是把所有的边都连边, 然后跑最小生成树, 当上下边界联通的时候, 最后那条边的长度就是球的最大直径

沙茶的 代码

注意%f会给你自动四舍五入...

1 最小生成树

一开始想先跑出树来然后跑LCA云云

后来参照吴清月大爷的做法感觉肥肠简短Orz

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define MAXN (500 + 5)
#define DD double
#define pii pair<int, int>
const int s = 0, t = 501;
using namespace std;
struct edg
{
	int from, to;
	DD cost;
	edg() {}
	edg(int a, int b, DD c): from(a), to(b), cost(c) {}
}b[MAXN * MAXN];
int fa[MAXN], n, cntb, l;
pii a[MAXN];
int find(int x)
{ return (fa[x] == x) ? x : (fa[x] = find(fa[x])); }
void uni(int x, int y)
{ fa[find(x)] = find(y); }
bool cmp(edg x, edg y)
{ return x.cost < y.cost; }
DD caldis(int x0, int y0, int x1, int y1)
{ return sqrt((x0 - x1) * (x0 - x1) + (y0 - y1) * (y0 - y1)); }
void solve()
{
	sort(b + 1, b + cntb + 1, cmp);
	for (int i = s; i <= t; i++)	fa[i] = i;
	for (int i = 1; i <= cntb; i++)
		if (find(b[i].from) != find(b[i].to))
		{
			uni(b[i].from, b[i].to);
			if (find(s) == find(t))
			{
				printf("%.3lf", b[i].cost);
				return ;
			}
		}
}
int main()
{
	scanf("%d%d", &n, &l);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d%d", &a[i].first, &a[i].second);
		b[++cntb] = edg(s, i, l - a[i].second);
		b[++cntb] = edg(t, i, a[i].second);
		for (int j = 1; j < i; j++)
			b[++cntb] = edg(i, j, caldis(a[i].first, a[i].second, a[j].first, a[j].second));
	}
//	cout << cntb << endl;
	solve();
	return 0;
}

2 二分

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define MAXN (500 + 5)
#define eps (0.000001)
#define DD double
#define pii pair<int, int>
const int s = 0, t = 501;
using namespace std;
int fa[MAXN], n, l;
pii a[MAXN];
void init()
{ for (int i = s; i <= t; i++)	fa[i] = i; }
int find(int x)
{ return ((x == fa[x]) ? x : (fa[x] = find(fa[x]))); }
void uni(int x, int y)
{ fa[find(x)] = find(y); }
DD caldis(int x0, int y0, int x1, int y1)
{ return sqrt((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0)); }
bool pd(DD x)
{
	init();
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (i != j && caldis(a[i].first, a[i].second, a[j].first, a[j].second) < x + eps)
				uni(i, j);
	for (int i = 1; i <= n; i++)
	{
		if (l - a[i].second <= x)
			uni(s, i);
		if (a[i].second <= x)
			uni(i, t);
	}
		
	return !(find(s) == find(t));
}
void ef()
{
	DD le = 0, ri = 100000;
	while (ri - le >= eps)
	{
		DD mi = (le + ri) / 2;
		if (pd(mi))
			le = mi;
		else
			ri = mi;
	}
	printf("%.3f", le + 0.0005);
}
int main()
{
	scanf("%d%d", &n, &l);
	for (int i = 1; i <= n; i++)
		scanf("%d%d", &a[i].first, &a[i].second);
	ef();
	return 0;
}

By 联赛钦定爆零的 Cansult