正解其实是\(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]\]
就是这样啦～
Luogu P4306 [JSOI2010]连通数 传递闭包
原文地址：https://www.cnblogs.com/maomao9173/p/10441146.html