mydcwfy's Blog

CF1335F

Posted on
Symbols count in article: 3k Reading time ≈ 7 mins.

基环树的简单题目。

1. 题意

  • 给定一个 $n\times m$ 的黑白网格，每一个点都会有一个方向，如果放置的机器人走到这里的话，将会按照该方向走下去。现在要放置最多的机器人，使得机器人永远不会走到同一个点上（每一步中间相遇的不算）。在放置最多的基础上，要求最开始放在黑色上的机器人最多。
  • 有 $t$ 组数据，$n\times m\leq10^6,\sum n\times m\leq10^6,t\leq5\times10^4$。

2. 思路

其实如果想到图论的话，就比较简单了。

首先，我们考虑怎样才能 永远不相撞。

所有的机器人最后一定是在环上一直绕圈，又由于速度相同，所以永远不会相撞。

易得第一问答案不可能大于环上点的数量（因为如果有多的话，走到最后，一定会有两个机器人在同一个点，明显不符合条件）。

注意到每一个点有且只有一个出边，所以原图一共有 $n\times m$ 个点，同样也有 $n\times m$ 条边。

？这不就是基环树吗？

通过基环树的方法，我们可以简单的找出所有的环。不考虑第二问的话，我们直接将所有的机器人放在环上，这个就是一个最优解。

那么第一问就解决了，答案就是环的数量。

下面我们来看第二问：怎样让最多的机器人在黑色点上？

已经是黑色点的我们可以不管了，我们可以将一些白色的点替换为非环的黑点。

我们画一个图，来看一下需要满足什么样的条件才可以。

当前，如果我们将一个机器人放在 b 点，经过两步之后，就会走到 c 点，如果最开始放在 a 点，也会走到 c 点。

所以其实 a 点和 b 点是等价的，换句话说，他们最后在环上的位置是等价的。

推广一下，对于任意一个点，假设他向上走走到环里需要的步数为 $x$，那么他就等价于环里距他最近的点往回走 $x$ 步得到的点。

转化为代码，就是：cir[((dep - from) % sz + sz) % sz + 1]，其中 $cir$ 存的是环的编号，从 1 开始，$sz$ 是指环的大小，$from$ 是指离他最近的点是环中的第几个。

这几个都是可以在第二次遍历基环树的时候很简单的得到。具体可以看代码。

3. 代码

注意由于有多组数据，不能使用 memset 之类的，而且读入的时候要直接转化为基环树上的编号。

码风略丑，请见谅。

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1e6 + 10, M = N << 1;
int h[N], e[M], ne[M], idx;
int cir[N], tot, ed[N], cnt, fu[N];
int n, m, blk[N];
char str[N];
bool ins[N], vis[N], onc[N], abl[N];

void dfs_c(int x, int from)//找环
{
	ins[x] = vis[x] = true;
	for (int i = h[x]; ~i; i = ne[i])
	{
		int j = e[i];
		if (i == (from ^ 1)) continue;
		fu[j] = x;
		if (!vis[j]) dfs_c(j, i);
		else if (ins[j]){
			for (int k = x; k != j; k = fu[k]) cir[++ cnt] = k, onc[k] = true;
			cir[++ cnt] = j, onc[j] = true;
			ed[++ tot] = cnt;
			if ((i & 1)) reverse(cir + ed[tot - 1] + 1, cir + ed[tot] + 1);
		}//注意此时如果 i & 1 的话，找到的环和我们的环是相反的，我们要调换过来
	}
	ins[x] = false;
}

void dfs_d(int x, int cirst, int dep, int sz)//cirst 表示环在 cir 数组里开始的位置，dep 是指当前的深度（我为了方便，加上了出发点的编号，方便直接计算，无需多余传参）
{
	abl[cirst + (dep % sz + sz) % sz] |= blk[x];
	vis[x] = 1;
	for (int i = h[x]; ~i; i = ne[i])
	{
		if (vis[e[i]] || onc[e[i]]) continue;
		dfs_d(e[i], cirst, dep - 1, sz);
	}
}

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void link(int a, int b){add(a, b), add(b, a);}
int get(int i, int j){return (i - 1) * m + j;}//转换编号

int main()
{
	int t;cin >> t;
	while (t --)
	{
		scanf("%d %d", &n, &m);
		idx = cnt = tot = 0;
		for (int i = 1; i <= n * m; ++ i) h[i] = -1, blk[i] = onc[i] = abl[i] = 0;
		for (int i = 1; i <= n; ++ i)
		{
			scanf("%s", str + 1);
			for (int j = 1; j <= m; ++ j) blk[get(i, j)] = str[j] == '0';
		}
		for (int i = 1; i <= n; ++ i)
		{
			scanf("%s", str + 1);
			for (int j = 1; j <= m; ++ j)
				switch (str[j])
				{
					case 'L' : link(get(i, j), get(i, j - 1));break;
					case 'R' : link(get(i, j), get(i, j + 1));break;
					case 'U' : link(get(i, j), get(i - 1, j));break;
					case 'D' : link(get(i, j), get(i + 1, j));break;
				}
		}
		for (int i = 1; i <= n * m; ++ i) vis[i] = 0;
		for (int i = 1; i <= n * m; ++ i)
			if (!vis[i]) dfs_c(i, -1);
		for (int i = 1; i <= n * m; ++ i) vis[i] = 0;
		for (int i = 1; i <= tot; ++ i)
			for (int j = ed[i - 1] + 1; j <= ed[i]; ++ j) dfs_d(cir[j], ed[i - 1] + 1, j - ed[i - 1] - 1, ed[i] - ed[i - 1]);
		int tblk = 0;
		for (int i = 1; i <= cnt; ++ i) tblk += abl[i];
		printf("%d %d\n", cnt, tblk);
	}
	return 0;
}