BZOJ3108 [CQOI2013] 图的逆变换
2018 年 03 月 14 日发布.
Description
定义一个图的变换:对于一个有向图$G=(V, E)$,建立一个新的有向图:
$V'=\{v_e|e \in E\}$,$E'=\{(v_b, v_e)|b=(u,v), e=(v,w)\}$,$G'=(V', E')$。
也就是说每个边变成一个点,如果边b的终点和边e的起点相同则b到e连一条边。
现在给定$G'$,问是否存在$G$。$G'$的点数不超过$300$。
Solution
如果$G'$中有$(u,w), (v,w)$两条边,那么说明$G$中$u,v$的终点相同;那么$G'$中$u,v$连到的点应该是一样的。
也就是说,如果我在$G'$中令$S_i$表示$i$连到的点集,那么$S_i=S_j$和$S_i\cap S_j$必有一成立。
反之,如果上述条件成立,我可以把所有点按照$S$划分,即可得到$G$中每个点的出边集合;然后容易找出$G$中每个点的入边集合,易证这个$G$是合法的。
于是bitset求出$S$之后枚举$i,j$判断即可。
Code
#include <bitset>
#include <cstdio>
const int N = 305;
std::bitset<N> out[N], zero;
int main() {
int T;
("%d", &T);
scanfwhile (T--) {
int n, m;
("%d%d", &n, &m);
scanf.reset();
zerofor (int i = 0; i < n; ++i) out[i].reset();
for (int x, y; m; --m) {
("%d%d", &x, &y);
scanf[x].set(y);
out}
bool ok = true;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
= ok && ((out[i] & out[j]) == zero || out[i] == out[j]);
ok (ok ? "Yes" : "No");
puts}
return 0;
}