BZOJ3108 [CQOI2013] 图的逆变换

Description

定义一个图的变换:对于一个有向图G=(V,E)G=(V, E),建立一个新的有向图:

V={veeE}V'=\{v_e|e \in E\}E={(vb,ve)b=(u,v),e=(v,w)}E'=\{(v_b, v_e)|b=(u,v), e=(v,w)\}G=(V,E)G'=(V', E')

也就是说每个边变成一个点,如果边b的终点和边e的起点相同则b到e连一条边。

现在给定GG',问是否存在GGGG'的点数不超过300300

Solution

如果GG'中有(u,w),(v,w)(u,w), (v,w)两条边,那么说明GGu,vu,v的终点相同;那么GG'u,vu,v连到的点应该是一样的。

也就是说,如果我在GG'中令SiS_i表示ii连到的点集,那么Si=SjS_i=S_jSiSjS_i\cap S_j必有一成立。

反之,如果上述条件成立,我可以把所有点按照SS划分,即可得到GG中每个点的出边集合;然后容易找出GG中每个点的入边集合,易证这个GG是合法的。

于是bitset求出SS之后枚举i,ji,j判断即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bitset>
#include <cstdio>
const int N = 305;
std::bitset<N> out[N], zero;
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n, m;
scanf("%d%d", &n, &m);
zero.reset();
for (int i = 0; i < n; ++i) out[i].reset();
for (int x, y; m; --m) {
scanf("%d%d", &x, &y);
out[x].set(y);
}
bool ok = true;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
ok = ok && ((out[i] & out[j]) == zero || out[i] == out[j]);
puts(ok ? "Yes" : "No");
}
return 0;
}