正解其实是\(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]\]

就是这样啦～