P4306 [JSOI2010]连通数

P4306 [JSOI2010]连通数

缩点后统计答案可以在 $O(n + m)$ 的时间内完成，但是由于题目的 $m$ 最大可以为 $O(n ^ 2)$ ，所以这样做复杂度为 $O(n ^ 2)$ 。

判断连通性可以传递闭包，传递闭包可以用 bitset 优化。可以做到 $O(\frac {n ^ 3} \omega)$ 。

查看代码

#include <iostream>
#include <cstdio>
#include <bitset>
using namespace std;
const int N = 2e3 + 10;
int n, res;
bitset <N> d[N];
int main ()
{
    char c;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            cin >> c;
            if (c == '1' || i == j)
                d[i][j] = true;
        }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            if (d[i][k]) d[i] |= d[k];
    for (int i = 1; i <= n; i++)
        res += d[i].count();
    cout << res;
    return 0;
}