Blog of RuSun

OneProblemIsDifficultBecauseYouDontKnowWhyItIsDiffucult

P4306 [JSOI2010]连通数

P4306 [JSOI2010]连通数

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

判断连通性可以传递闭包,传递闭包可以用 bitset 优化。可以做到 O(n3ω)

查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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;
}

Gitalk 加载中 ...