正解其实是 \(Tarjan\) + \(拓扑拓扑 \), 但是却可以被 \(O(N^3 / 32)\) 复杂度的传递闭包水过去. 心疼一下写拓扑的小可爱们.
学到一个 \(bitset\) 优化布尔图的骚操作, 直接压进去乱搞, 能快不是一点.
(基本上就是差了一个 \(log\))
先放代码.
- #include <bits/stdc++.h>
- using namespace std;
- int n; char s[2010];
- bitset <2010> mp[2010];
- int main () {
- cin>> n;
- register int i, j, k;
- for (i = 0; i <n; ++i) {
- scanf ("%s", s);
- for (j = 0; j <n; ++j) {
- mp[i][j] = s[j] - '0';
- }
- }
- for (k = 0; k <n; ++k) {
- for (i = 0; i <n; ++i) {
- if (mp[i][k]) mp[i] |= mp[k];
- }
- }
- int ans = 0;
- for (i = 0; i <n; ++i) ans += mp[i].count ();
- cout <<ans <<endl;
- }
上一份传递闭包的代码中, 我们写的是一个标准的 \(floyd\), 为什么到这里就把第三层循环省略了呢?
当且仅当 \(mp[i][k]==1\) 时,\(mp[k]\) 的相关关系才可以通过 \(mp[i][k]\) 进行传递, 而且传递的方式刚好是按位对应.
\[to[i][j] |= (to[i][k] \& to[k][j]) -> if (to[i][k]) to[i] |= to[k]\]
就是这样啦~
来源: http://www.bubuko.com/infodetail-2969209.html